Explain the Myhill-Nerode Theorem

Mumbai university > Comp > SEM 4 > TCS

Marks: 5M

Year: Dec 2014,May 2014

  • The Myhill-Nerode theorem is an important characterization of regular languages, and it also has many practical implications.

  • One consequence of the theorem is an algorithm for minimizing DFAs which is a vital step in automata theory

  • Theorem:

    The MyhillNerode Theorem states that for a language L such that L C Σ*, the following statements hold good :-

    • There is a DFA that accepts L(L is regular)

    • There is a right invariant equivalence relation ~ of finite index such L is a union of some of the equivalence classes of ~.

    • ~L is of finite index.


enter image description here

Step 1: Consider every final-nonfinal state pair and tick it working only on the lower triangular part of the table

enter image description here

Step 2: Consider all the un-ticked areas of step1

For an input(either a or b) for each un-ticked state, see the intermediate state For the area (r,t):

(r,a) => {r} and (t,a) =>s

So, here the intermediate state is ‘s’

Now check if {r,s} is ticked in step1.

If yes, tick {r,t} as well.

Similarly, {q,u} and {r,q} are also ticked

Step3: Continue step2 until all states have been processed. Once no more can be ticked, algorithm terminates.

Hence, here {s,u} is also ticked.

Final table now becomes

enter image description here

Step 4: Check the spaces which are still un-ticked and such states can be merged together.

In the final minimized DFA, q-s are the new states and p-t are the new states

Please log in to add an answer.

Continue reading

Find answer to specific questions by searching them here. It's the best way to discover useful content.

Find more