Question

Write a short note on myhill nerode theoram

Answer 1

In the theory of formal languages, theMyhill–Nerode theorem provides anecessary and sufficient condition for a language to be regular. The theorem is named for John Myhill and Anil Nerode, who proved it at the University of Chicago in 1958 (Nerode 1958).

Statement of the theoremEdit

Given a language L, and a pair of stringsx and y, define a distinguishing extension to be a string z such that exactly one of the two strings xz and yzbelongs to L. Define a relation RL on strings by the rule that x RL y if there is no distinguishing extension for x and y. It is easy to show that RL is anequivalence relation on strings, and thus it divides the set of all strings intoequivalence classes.

The Myhill–Nerode theorem states thatL is regular if and only if RL has a finite number of equivalence classes, and moreover that the number of states in the smallest deterministic finite automaton (DFA) recognizing L is equal to the number of equivalence classes inRL. In particular, this implies that there is a unique minimal DFA with minimum number of states (Hopcroft & Ullman 1979).