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.

$\endgroup$
3
  • $\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, 2018 at 11:16
  • $\begingroup$ You searched but didn't find our reference question? That sounds unlikely. $\endgroup$
    – Raphael
    Jan 29, 2018 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, 2018 at 12:39

3 Answers 3

1
$\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}$.

$\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)$

$\endgroup$
2
  • $\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, 2018 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$ Jan 29, 2018 at 13:15
0
$\begingroup$

i can't comment as i haven't yet touched the benchmark of 50 reputations.

I would like to make your work a bit clearer.You have used 3 variables although even 2 are sufficient .

a^n! let n=m ,

now consider this, |w|=|xz|+i|y|

also , m! has two parts k! = |xz| and j = i.|y|

now we know j<=m , considering m is not < 3 (smaller than 3)

m!-j=k! (it is needed to make sure xz exists )

now , the same thing ,

it is impossible for it to exist,

as n!-j >= n!-n > (n-1)! (how did it happen ? see below)

n!-n = n(n-1)!-n = n((n-1)!-1) > (n-1)!

therefore it's not regular .

alternative way to check identify RL is : (credits to Seemona A for this short algo )

  1. 1.If given language is finite => Regular
  2. If language is infinite: Language over one symbol : Forms AP => Regular ; Doesn't form AP => Not Regular ;; Language over more than one symbol : No dependency => Regular; Dependency => Not Regular;;

another logic is L(G)+{a^n! , n>=0} has set of elements which are not periodic in nature . a grammar on single variable is CFG if it is RegG

And a grammar is RegG iff there is a periodic nature in the set of elements of its language.

similarly if we try for CFL(context free) , we can substitute (p+r) and still the logic will be same as the string to be pumped are v= a^p and y= a^r . Logic will remain the same

https://qr.ae/pvVy55 , user named "Seemona A" has nicely concluded in short (it's a "quora" site link , a general QnA networking site).

https://john.cs.olemiss.edu/~hcc/csci311/notes/ (here you can also find it in regular expression section...... Ole Miss is University of Mississippi )

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.