[Solved]: What are some good hints for proving non-regularity with the pumping lemma?

Problem Detail: 

My CS Theory Professor said that when proving that a language is not regular by the Pumping Lemma, that there are some 'tricks' for solving languages more complicated that something like $L = \{a^{n} b^{n}\mid n \in\mathbb{N}\}$. Although I know that these come with practice, I wondered if this community would have some input on the matter?

If you don't quite know what I am asking, think to calculus, when your professor used something that HE knew would get you from point a to point b that if YOU don't know, you cannot solve the problem.

Asked By : Danielle

Answered By : A.Schulz

Always notice that you apply the reverse direction of the implication stated in the lemma when proving non-regularity. That is for any $k\in \mathbf{N}$ you pick a word $w\in L$ (depended on $k$) that has length at least $k$ and there is no way to split the word into three parts, such that pumping the middle parts in or out keeps the word in the language. Notice that you only consider partitions where the first two words together have length $k$ or less, and of course the middle part is not the empty word.

So here are a few general ideas.

1. Keep in mind that you pick the word dependent on $k$, so $k$ usually appears in the word $w$ as a parameter. For example in $\{a^nb^n \mid n\ge 0\}$ you pick $w=a^kb^k$.

2. It is crucial to pick the right word $w$. Pick a word that has an easy structure. Make it as easy as possible.

3. Notice that you are only allowed to pump at the beginning of the word. Use this restriction, by choosing a word in which the first $k$ letters have a simple structure.

4. For unary languages like $\{a^{n^2}\mid n\ge 0\}$ pick a very large word and hope that the distance to the next word in $L$ is larger than $k$. In the example pick $w=a^{k^2}$, the the next larger word in $L$ is $a^{(k+1)^2}$, but $(k+1)^2-k^2=2k+1$. Pumping the middle words once, gives a word that is too short. Another idea for unary languages is to pick $i$ in terms of $k$.

5. Don't forget to cover the case of pumping the middle word out.

You can see the (reverse direction) of pumping lemma as a two player game. Someone picks a $k$ then you pick the $w\in L$, then he splits the $w$ according to the rules, then you pick a repetition of the middle word. If the pumped word is not in the language then you win. If this game has a winning strategy for you, then $L$ is not regular.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/8957

3.2K people like this

 Download Related Notes/Documents