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.