Myhill Nerode versus Pumping Lemma
I have seen some recent backlash against the pumping lemma for showing that languages are not regular and as I am now teaching regular languages I had to choose should I teach the pumping lemma or Myhill-Nerode to show languages are not regular. Let's review both definitions (taken from Wikipedia)
Pumping Lemma: If a language L is regular, then there exists a number p ≥ 1 (the pumping length) such that every string uwv in L with |w| ≥ p can be written in the form uwv = uxyzv with strings x, y and z such that |xy| ≤ p, |y| ≥ 1 and uxyizv is in L for every integer i ≥ 0.
Myhill-Nerode: Given a language L, and a pair of strings x and y, define a distinguishing extension to be a string z such that exactly one of the two strings xz and yz belongs 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 an equivalence relation on strings, and thus it divides the set of all finite strings into equivalence classes.
The Myhill–Nerode theorem states that L 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 in RL. In particular, this implies that there is a unique minimal DFA with minimum number of states.
The two basic complaints about the pumping lemma: Five quantifiers and it is not complete--there are nonregular languages that can be pumped. To the first point if you think of the pumping lemma as a game with the adversary choosing p, x, y and z, the quantification is not as confusing as some would think. Myhill-Nerode also has five quantifiers when you spell it out: For all regular L, there exist x1,...,xk such that for all y there is an i such that for all z, xiz is in L iff yz is in L.
As to the second part, the counterexamples are contrived and usually go away with simple closure properties. Consider the one from wikipedia:
Take L ∩ (01(2∪3))* eliminates the strings in the first part of L and now it is easy to pump.
So I don't buy the arguments for Myhill-Nerode over pumping. Nevertheless I'll teach the pumping lemma and Myhill-Nerode because they are both so cool.
Pumping Lemma: If a language L is regular, then there exists a number p ≥ 1 (the pumping length) such that every string uwv in L with |w| ≥ p can be written in the form uwv = uxyzv with strings x, y and z such that |xy| ≤ p, |y| ≥ 1 and uxyizv is in L for every integer i ≥ 0.
Myhill-Nerode: Given a language L, and a pair of strings x and y, define a distinguishing extension to be a string z such that exactly one of the two strings xz and yz belongs 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 an equivalence relation on strings, and thus it divides the set of all finite strings into equivalence classes.
The Myhill–Nerode theorem states that L 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 in RL. In particular, this implies that there is a unique minimal DFA with minimum number of states.
The two basic complaints about the pumping lemma: Five quantifiers and it is not complete--there are nonregular languages that can be pumped. To the first point if you think of the pumping lemma as a game with the adversary choosing p, x, y and z, the quantification is not as confusing as some would think. Myhill-Nerode also has five quantifiers when you spell it out: For all regular L, there exist x1,...,xk such that for all y there is an i such that for all z, xiz is in L iff yz is in L.
As to the second part, the counterexamples are contrived and usually go away with simple closure properties. Consider the one from wikipedia:
Take L ∩ (01(2∪3))* eliminates the strings in the first part of L and now it is easy to pump.
So I don't buy the arguments for Myhill-Nerode over pumping. Nevertheless I'll teach the pumping lemma and Myhill-Nerode because they are both so cool.
No comments have been added yet.
Lance Fortnow's Blog
- Lance Fortnow's profile
- 4 followers
Lance Fortnow isn't a Goodreads Author
(yet),
but they
do have a blog,
so here are some recent posts imported from
their feed.
