0
Explain the Myhill-Nerode Theorem

Mumbai university > Comp > SEM 4 > TCS

Marks: 5M

Year: Dec 2014,May 2014

0  upvotes
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  upvotes
Please log in to add an answer.

Next up

Read More Questions

If you are looking for answer to specific questions, you can search them here. We'll find the best answer for you.

Search

Study Full Subject

If you are looking for good study material, you can checkout our subjects. Hundreds of important topics are covered in them.

Know More