3
$\begingroup$

Let $L$ a language over $X = \{a\}$ defined as follow :

$$L = \{ a^{n!} \ | \ n \geq 0 \}$$

I want to prove that $L$ isn't regular, I have searched in the forum for an equivalent question, but I found nothing. If it's a duplicate, I apologize and I'll be glad if you provide me the link of the duplicated question.

I'll show here what I have done, using the pumping lemma.


Suppose that $L$ is regular, let $n \in \mathbb{N}^*$ and $\omega = a^{n!}$. We have $\omega \in L$ and $|\omega| \geq n$. Thus, there exist $x, y, z \in X$ so as :

  1. $a^{n!} = xyz$
  2. $y \neq \epsilon$
  3. $|xy| \leq n$
  4. $xy^kz \in L, \quad \forall k \geq 0$

Because of fact 3, $xy = a^k$ and $y = a^j$ with $k \leq n$ and $1 \leq j \leq n$. Thus :

$$a^{n!} = a^{k - j}.a^{j}.a^{n! - k}$$

By fact 4, we must have $a^{k - j}.a^{n! - k} = a^{n! - j} \in L$.

In addition, because $1 \leq j \leq n$, the following is true :

$$n! - n \leq n! - j \lneq n!$$

The final result that I need is that $(n - 1)! \lneq n! - n$. Using this I can deduce :

$$(n - 1)! \lneq n! - j \lneq n!$$

Showing that $n! - j$ can't be the factorial of an integer, giving the contradiction $a^{n! - j} \notin L$. I have tried to prove the final result, but I didn't succeed. It is not true for the first values of $n$, I have tried to consider multiple cases but went for nothing.

So I ask for your advice, maybe I am going wrong and didn't applied the pumping lemma with a word that leads to contradiction.

| cite | improve this question | | | | |
$\endgroup$
  • $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$ – Raphael Jan 29 '18 at 11:16
  • $\begingroup$ You searched but didn't find our reference question? That sounds unlikely. $\endgroup$ – Raphael Jan 29 '18 at 11:16
  • 1
    $\begingroup$ @Raphael In the reference question, I didn't find a way to finish my proof, because in this case the question is very tight to the properties of the factorial. Also I didn't ask if my answer is correct because it's an unfinished proof, I asked for a way to finish it or for help to find another proof. $\endgroup$ – user80502 Jan 29 '18 at 12:39
0
$\begingroup$

The easiest way is probably to use the pumping lemma on the complement language $\overline{L} = \{ a^m : m \neq n! \}$. Suppose that $L$ were regular. Than $\overline{L}$ would be regular. According to the pumping lemma, there is a pumping length $p$ such that every word $w$ of length at least $p$ in $\overline{L}$ has a decomposition $w = xyz$ such that $|xy| \leq p$, $y \neq \epsilon$, and $xy^iz \in \overline{L}$ for all $i \geq 0$. Take $w = a^{p\cdot p!} \in \overline{L}$ (without loss of generality, $p > 1$). Suppose that the decomposition is $w=xyz$, where $y=a^t$. Since $t \leq p$, it follows that $t \mid p!$. But then $xy^{1+p!/t}z = a^{p\cdot p! + p!} = a^{(p+1)!} \notin \overline{L}$.

| cite | improve this answer | | | | |
$\endgroup$
0
$\begingroup$

It is a little confusing that you seem to have used $k$ in two different ways. First in the pumping lemma $xy^kz$, then to fix the length of $xy$.

Rather than trying to prove that deleting $y$ from the string $\omega$ (pumping with $k=0$) will give a string outside the language, perhaps it is easier to add a copy of $y$ (pumping with $k=2$).

$n!+j \le n!+n < n!(n+1)$

| cite | improve this answer | | | | |
$\endgroup$
  • $\begingroup$ $n! + n \lneq n!(n+1)$ doesn't hold for $n = 0 \lor n = 1$, but those special cases are easy to handle. With the addition that $n! \lneq n! + j$, we finish the proof. Thank you ! $\endgroup$ – user80502 Jan 29 '18 at 11:16
  • 1
    $\begingroup$ @AbdousKamel True. When using the Pumping Lemma you can avoid small strings by assuming the pumping constant $n$ "is large enough". Here we set $n>2$. $\endgroup$ – Hendrik Jan Jan 29 '18 at 13:15

Your Answer

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