Talk:Myhill–Nerode theorem

From Wikipedia, the free encyclopedia

Removed.

[edit] Example proof of non-regularity

Consider the language . Now consider the infinite set of strings . For any two strings from this set x = aⁱ, y = a^k with i < k, we can append z = b^k to each, which results in xz = aⁱb^k, which is not in L, and yz = a^kb^k, which is in L. Thus each string of the form aⁱ belongs to a different equivalence class, so there are an infinite number of equivalence classes defined by the language, and so by the Myhill-Nerode Theorem it is not regular.

Note that this language can be "pumped" in the sense that any nonempty string in the language can be expanded by replacing a single a with arbitrarily many copies of a. The language thus gives an example of a non-regular language that cannot be shown to be non-regular using the pumping lemma.

This is false. The pumping lemma requires it to be true for the case i = 0 as well. So say the string is a^pb^p If the y portion of the string is aⁿ, then removing it would get the string a^{p − n}b^p, which is not in the language since if n > 1 (required by the condition for y being nonempty), then p > p − n, so it is not in the language. Therefore, it can not be pumped, so the Myhill-Nerode Theorem is not required.

As suggested by Michael Sipser, the language F = { and if i = 1 then j = k}, can be pumped (including for the case where the y portion is ommitted), but is not regular, might be a canidate for using the Myhill-Nerode Theorem. Jrincayc 17:11, 21 Mar 2004 (UTC)

[edit] Unintuitive formal definition

While the current version of the article may be cleaner from a formal point of view, IMO it's highly unintuitive. My initial version, explaining it in terms of FSM states and alluding to a simple proof by the pigeonhole principle is much more intuitive (again, IMO). Any ideas on how to integrate this? --Delirium 22:36, Sep 9, 2004 (UTC)

[edit] Not Helpful

As a grad student trying to understand Myhill-Nerode I find the description not at all helpful. Delerium's definition contains the following:

"..two strings x and y are said to belong to the same equivalence class if they both drive a given machine to the same state q. A consequence of this is that for any string z, xz and yz drive the machine to the same state q'. Since a finite state machine has a finite number of states, there can only be a finite number of such equivalence classes (a proof readily follows from the pigeonhole principle). This observation constitutes the Myhill-Nerode Theorem: A language is regular if and only if the set of equivalence classes defined by the language is finite."

It's more illuminating than what is currently posted.

I also think an example of each case (regular vs non-regular) would be very useful for those of us who learn by example.Myrikhan (talk) 20:45, 7 February 2008 (UTC)