Automaton-Based Substring Algorithm

**Automaton Design**

The number of states in the automaton must grow with the length of the target substring. A substring of 20 characters, for example, requires an automaton with 21 states.

An important point is that repeated patterns must return to the relevant state rather than always returning to Q0. This allows repeated substrings such as 00 and AliAli to be accepted correctly.

The algorithm therefore generates an automaton specifically for each substring. The example automaton accepts only the substring ababaca. Q1 is reached when the appropriate a transition occurs, and comparable rules apply to the other states.

A repeated pattern such as baba requires returning to the start of the repeated section instead of Q0.

Project Features

• Real-time validation
• Form background color based on acceptance state
• Automatic generation of an automaton for the target substring
• Automaton-validity checking
• Support for repeated substrings
• Detailed display of followed transitions

Project Details

When the program opens, the first text box receives the source string and the second receives the substring. Their TextChanged events invoke the required functions. The islem() function passes the relevant values to Kokersubstr() and changes the text-box backgrounds according to the returned value: green when accepted and red when rejected. It also writes the traversed states to the third text box.

Kokersubstr() performs the automaton-based substring matching. It returns false for an empty string. Otherwise, the current state is stored in the variable q and the input string is scanned in a loop. When the current character matches, the git() function advances the state. When q reaches b.length, the final state has been reached and the function returns true.

When a character does not match, the algorithm first checks for repetition. If the current state contains a repeated form such as 00, 000 or AliAli, the repetition is detected in a loop and execution returns to the appropriate state. When no repetition exists, the bas variable remains true and the automaton returns to state 0. The function therefore returns true when the automaton accepts the substring and false otherwise.

The git() function changes the static state variable q and appends the followed transitions to the string variable s3. The kontrol() function identifies every substring of the string entered in the relevant text box and passes them to Kokersubstr() to validate the automaton. Nested loops divide a string such as 012 into 0, 01, 012, 1, 12 and 2. The relevant event functions are then defined, and the worker thread is terminated when the form closes.