Search code examples
algorithmstring-matchingfinite-automataclrs

Is my transition function correct (String matching with finite automata)

I am learning String matching with finite automata from CLRS . I am solving some exercise problems .For the exercise problem 32.3-1 ,

Construct the string-matching automaton for the pattern P = aabab and illustrate its operation on the text string T = aaababaabaababaab.

the following is my transition function ,

states   a   b
 0       1   0
 1       2   0
 2       2   3
 3       4   3
 4       4   5
 5       ?   ?

Is my transition function correct ? And how do i fill the last row ? Any help

Solution

  • I assume you are creating a Finite Automata which accepts a string containing the pattern aabab.

    There are two mistakes in your finite automata,

    on state 3 and state 4,

    For state 3, if the input is b, you have to go back to state 0. For example the pattern aabb will force you back to state 0. Here you have to start all over again from state 0.

    For state 4, if the input is a, you have to go back to state 2 because you have the pattern aa. For example the pattern aabaa will force you back to state 2.

    The corrected Finite Automaton is given below,

    states   a   b
 0       1   0
 1       2   0
 2       2   3
 3       4   0
 4       2   5
 5       5   5

    Here 5 is your Accepting state. You will reach this state only when you have found the required pattern in a string. Once a pattern is found no matter what the string remains in the accepting state. Hence for both inputs a and b on state 5 remains on 5 itself.

    The transition function is that of an fa accepting a string with sub string 'aabab'. If you are going back to state 1 for a and 0 for b, then the transition function accepts strings ending with the sub string 'aabab'. Given that only state 5 is the accepting state.