4 ms·
The canonical example for pumping lemma disproof is a^n b^n, which is more obvious IMO.
by chakkepolja 5y ago
The canonical example for pumping lemma disproof is a^n b^n, which is more obvious IMO.
- thaumasiotes 5y agoHere are the disproofs: ----- (1) a^n b^n The pumping lemma tells us that for some string in this language, we can divide the string into three substrings x y z such that x y^n z remains in the language for all n. There are two cases: (1)(a) The number of 'a' characters in y does not equal the number of 'b' characters. In this case, pumping y will violate the constraint that a string in the language must have an equal number of 'a's and 'b's. (1)(b) y consists of k 'a's followed by k 'b's for some k > 0. In this case, pumping it will violate the constraint that for every string in this language, each 'a' character must precede every 'b' character. Thus, the language a^n b^n is not regular. ----- (2) a^n, where n is prime The pumping lemma tells us that for some string in this language, we can divide the string into three substrings x y z such that x y^n z remains in the language for all n. [same as above] But the string x y^|xz| z has length |xz| + |y|*|xz|, which is not prime. Thus, the language a^n (where n is prime) is not regular. ----- Which of those was easier?
- chakkepolja 5y agoThe proof for a^n b^n, as I was taught, being that -> there exists a integer N such that pumping lemma holds for any w in L longer than L. (That is we can divide w into xyz and pump y, where |xy| ≤ n, and y is nonempty). -> now consider a^N b^N, we cant divide it into xyz such that we can pump y and w still remains in a^n b^n.