Peter Linz Edition 4 Exercise 4.3 Question 11 (Page No. 123)

Question

Show that the language

                    $L =$$\left \{ a^{n!} : n\geq 1 \right \}$ is not regular using pumping lemma

Comments

ankit we can't pick any value of m. also you are choosing y.

read this answer by arjun sir https://gateoverflow.in/207919/self-doubt-pumping-lemma

---

Thank you!

---

plz check

Answer 1

Suppose L is regular

Then there is a constant n, if z is any word in L and |z|>n, we may write z=uvw in such a way that $|uv|\leq n$ and $|v|\geq 1$ and for all $i\geq 0$ $uv^{i}w$ is in L

Now,$ a^{n!}$=$a^{n}$$^{\left ( n-1 \right )}$$^{\left ( n-2 \right )}$$^{....1}$

Here u=0

v=$ a^{n!}$=$a^{n}$$^{\left ( n-1 \right )}$$^{\left ( n-2 \right )}$$^{....1}$ which is forming more than one loop

w again will be 0

So, it cannot satisfy $v^{i}$ for more than one loop in $z=uv^{i}w$

Hence L is not regular

Comments

yes, and that is explained in stackoverflow answer beautifully

But my question is , why u r adding k

Something adding doesnot mean factorial

ryt?

factorial means breaks by multiplication, not by addition

So, rather adding I breaks the factorial by multiplication

Can u have a look my answer now and tell me if there is any mistake?

---

how can you state that u = 0? then after that how can you say that $v = a^{(n)(n-1)(n-2)...1}$

---

check my answer

Answer 2

Suppose L is regular

There exist some pumping length for L, let it be "m"

We don't know the value of m but whatever it is we can always choose n = m.

Then from the pumping lemma there exists $x, y, z \in Σ^{∗}$ such that w = xyz , |xy| ≤ m and |y| ≥ 1.

$w_{i} = xy^{i}z$

 y must contain entirely of a's

suppose $|y|=k$

the string obtained by i = 2 is,

w = $a^{m!+2k}$
we know that k $\geq$1 

so  if 1 $\leq$ k $\leq$ m

$m!$ $<$ $(m! + k)$ $<$ $(m+1)!$ 

hence we can say that $a^{m!+k}$ $\notin L$

Hence our assumption of L being regular was wrong and L is not regular.

Comments

srestha this proof needs some modification too and that answer on math.stackexchange is also not appropriate. wait let me think.

---

I want to know which part of string is x, which part is y and which part is z?
u have to break a single string in 3 parts in pigeon hole principle
right?

---

yes but pumping lemma doesn't need x,y,z explicitly 

check arjun sir's answer https://gateoverflow.in/207919/self-doubt-pumping-lemma

He is mentioning that if language is regular this decomposition must exist like 

for example L = $aa^{n}b$ 

we can see the decomposition and also the length of y and x and z. 

i was also confused for the same thing because how to prove if there are so many unknowns but we can