# How to prove by pumping lemma these languages are not regular?

1. $L_1 = (a^k * b^r \mid k \neq r^2)$

2. $L_2 = (a ^{\sum_i ^n t} \mid n > 0 )$

-
I'm not 100% sure I interpreted "(a ^(sigma from i to n) t | n > 0 )" correctly. Please switch it if I'm wrong. For one thing, the $t$ seems strange. – rschwieb Dec 21 '12 at 15:00
Are you sure that $i$ in the definition of $L_2$ isn't supposed to be $1$? It would make more sense, since if $i > 1$, we'd need to pick some meaningful definition for $\sum_{t=i}^n$ when $n < i$. – Ilmari Karonen Dec 23 '12 at 23:14

I realize that the assignment asked you to use the pumping lemma, but I always like to solve these kinds of problems using the pigeonhole principle directly, both because it's often easier and more informative than just blindly applying the pumping lemma without understanding what's really going on, and also because, frankly, I can never remember the exact statement of the pumping lemma for regular languages off the top of my head, whereas the pigeonhole principle is so simple and obvious that one can't really forget it. Besides, it can often do the job even in cases where the pumping lemma fails.

The basic idea is that a language $L$ is regular if and only if it is the language accepted by some DFA. Let that DFA have $n$ states. Informally, what we want to show is that an $n$-state DFA can only count up to $n$. Thus, if we can demonstrate that correctly accepting (only) the language $L$ would require distinguishing more than $n$ states, for any given $n$, then we've shown that $L$ cannot be regular.

For example, let's start with $L_1 = \{a^k b^r \mid k \ne r^2\}$. If this language were accepted by an $n$-state DFA, then by the pigeonhole principle, there would have to be two distinct numbers $i$ and $j$, with $0 \le i < j \le n$, such that the DFA would be in the same state after reading the strings $a^i$ and $a^j$. Now, let $r \ge \sqrt{i}$ and let $k = r^2$, so that $m = k - i \ge 0$. To reject any input not in $L_1$, the DFA must, in particular, reject the input $a^k b^r = a^i a^m b^r$. But this means that it must also reject the input $a^j a^m b^r$ which does belong to $L_1$, which means that $L_1$ cannot be the language it accepts. Since this holds for any DFA with any finite number of states, it follows that $L_1$ cannot be a regular language.

As for $L_2 = \{ a^{\sum_{t=1}^n t} \mid n > 0 \} = \{ a^1 a^2 \dots a^n \mid n > 0 \}$ (where I'm assuming you meant $1$ instead of $i$ for the reasons stated in my comment above), let $m$ be the number of states in the DFA supposedly accepting $L_2$ (since the variable $n$ is already in use) and consider the set of input prefixes $p_k = a^1 a^2 \dots a^{m-1} a^k$ for $0 \le k \le m$. There are $m+1$ such prefixes, so there must be two of them, $p_i$ and $p_j$ with $i < j$, such that the DFA ends up in the same state after reading each of them. But this means that, in order to accept the input $p_i a^{m-i} \in L_2$, it must also accept $p_j a^{m-i} \notin L_2$.

-
In my opinion it's really hard to forget exact statement of the pumping lemma if you really know what's going on there. It's just saying that if we look at DFA (with $n$ states) for regular language $L$ as on a directed graph of states of this DFA, then every word longer than $n$ needs to make a loop in this graph within first $n+1$ characters, and we can repeat that loop as long as we want to. So in $w=w_1w_2w_3$ the $w_2$ term corresponds to that loop. – Adam Dec 24 '12 at 12:38

Assume that $L_1$ is regular. Let $n$ be a constant from pumping lemma (it depends only on language!). Consider word $w=a^{n!}b^{n!}$ which is clearly in $L_1$. By pumping lemma there exists words $w_1$, $w_2$ and $w_3$ such that $w=w_1w_2w_3$, $|w_2|>0$, $|w_1w_2|\leq n$ and $\forall_{i\in\mathbb{N}}w_1w_2^iw_3\in L_1$. So $w_2=a^l$ for some $l\in\mathbb{N}$ (because first $n$ letters of $w$ are all $a$s). But then it is easy to see that we can choose $i$ such that $w_1w_2^iw_3 = a^{(n!)^2}b^{n!} \notin L_1$

Now use a similar argument to prove that $L_2$ is not regular

EDIT: How does pumping lemma works? It says that if language $L$ is regular then there exists magic constant $n$ such that we can split every word $w\in L$ longer than $n$, into three parts $w_1w_2w_3$ (with $|w_1w_2|\ge n$) and "pump" the middle term as much as we want always obtaining a word from $L$. So in order to prove that language is not regular all we have to do is to find a word which lacks this property.

For $L_1$ if we take $w=a^{n!}b^{n!}$ and split it into $w_1w_2w_3$, there must be $w_1=a^k$, $w_2=a^l$ and $w_3=a^{n!-k-l}b^{n!}$ (not just $b^{n!}$ as you posted in your comment) with $k+l\le n$. So how does $w_1w_2^iw_3$ look like? It's $$a^ka^{li}a^{n!-k-l}b^{n!}=a^{n!+(i-1)l}b^{n!}$$Can we find $i$ such that $a^{n!+(i-1)l}b^{n!}\notin L_1$? Yes, thanks to factorial. We have $l\le n$, so both $(n!)^2$ and $n!$ are divisible by $l$. We only need to solve equation $n!+(i-1)l=(n!)^2$ which gives us $$i=\frac{(n!)^2-n!}{l}+1$$ and it is indeed a natural number. This contradicts pumping lemma and shows that $L_1$ is not regular.

Different (simpler) approach: We can use a fact that language $L$ is regular iff it's complement $\bar{L}$ is regular. So it's sufficient to show that $\bar{L_1}=(a^kb^r|k=r^2)$ is not regular. So assume that $\bar{L_1}$ is regular and let $n$ be a constant from pumping lemma. Now looking at word $w=a^{n^2}b^n$ we see that if we split it into $w=w_1w_2w_3$ with $|w_1w_2|\le n$ then $w_2=a^k$ for some $k>0$ and $w_1w_2^2w_3=a^{n^2+k}b^n$ which is not in $\bar{L_1}$ because $n^2+k \neq n^2$

-
thanks but if you can change your answer becuase its : k != r^2 , not k! = r^2 ( k is not r * r) – user14988 Dec 21 '12 at 15:21
Yes, k is not equal r square :) That's the question I answered – Adam Dec 21 '12 at 22:00
I dont really understand, which i can i choose ? if i take w1 = a^s , w2 = a^t , t > 0 , s>= 0 , s + t <= n , and w3 =b^n! w1w2w3 = a^s* a^t * a ^ n! - s - t * b ^ n! whats next? – user14988 Dec 22 '12 at 0:35
why is $w_1w^i_2w_3 = a^{(n!)^2}b^{n!}$ ??? – user14988 Dec 23 '12 at 19:39
@user14988 there was a little mistake I have corrected. And I also included different solution. Is it ok now? – Adam Dec 24 '12 at 12:25