0
$\begingroup$

Show that the language

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

My solution is :

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 = 1 is,

w = $a^{m!+k}$


Now after this i'm stuck because how can i prove $m!+k$ cannot be accepted by the language

also if i chose i = 0 then also i'm stuck

$\endgroup$
1
$\begingroup$

Pick $i$ such that $m! + ik \neq h!$ for some $h$, and you are done. In particular, if $i=1$, then $m! + k \leq m! + m \neq (m+1)!$.

Your proof otherwise looks good!

$\endgroup$
  • $\begingroup$ but how can we pick k? are we allowed to pick k anywhere between $1 \leq k \leq m$ that helps in contradiction? $\endgroup$ – Mk Utkarsh Mar 20 '18 at 9:58
  • $\begingroup$ i read Introduction of formal languages and Automata by peter linz and we cannot choose the decomposition of string. correct me if i'm wrong $\endgroup$ – Mk Utkarsh Mar 20 '18 at 10:02
  • $\begingroup$ I misread your proof a little. You want to select $i$ appropriately. See my edit. $\endgroup$ – ml0105 Mar 20 '18 at 13:00
  • $\begingroup$ 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 = 1 is, w = $a^{m!+k}$ 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. $\endgroup$ – Mk Utkarsh Mar 20 '18 at 19:45
  • 1
    $\begingroup$ Pick $i=2$. Note that for $i=1$, $y^{i} = y$. $\endgroup$ – ml0105 Mar 20 '18 at 19:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.