0
Explain the Myhill-Nerode Theorem

Mumbai university > Comp > SEM 4 > TCS

Marks: 5M

Year: Dec 2014,May 2014

0
0
  • 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.

Example:

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

0
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