1
$\begingroup$

Use Nerode's theorem to prove that the following language $L$ is not regular:

$$ L=\{a^{k!} \mid 1\leq k\} $$

Here is my attempt:

Let $A$ be an infinte set of words s.t- $$ A=\{a^n \mid n\in \mathbb{N}\}$$

Then we shall consider 2 words from the set $a^{i!}$ and $a^j$ s.t-
$$ i!\leq n, i!\ne j$$

$$a^{i+1} \longrightarrow a^{i!}\cdot a^{i+1}=a^{(i+1)!}\in L$$ $$a^j\cdot a^{i+1}=a^{j+i+1}\notin L$$

I understand my attempt is not correct since when multiplying $a^{i!}\cdot a^{i+1}$ the exponent doesn't multiply . I cant seem to overcome this obstacle and would appreciate help.

$\endgroup$
3
  • $\begingroup$ I don't understand your attempt, since it doesn't contain any words. $\endgroup$ Dec 13, 2021 at 18:23
  • $\begingroup$ Also, what is your question? Is it whether your attempt is correct or not? We typically don't grade homework solutions, which is your TA's job. $\endgroup$ Dec 13, 2021 at 18:24
  • $\begingroup$ @YuvalFilmus I edited my attempt and clarified my question $\endgroup$
    – ATB
    Dec 13, 2021 at 18:36

1 Answer 1

0
$\begingroup$

You can prove the following using Myhill-Nerode: If $x_n$ is a non-decreasing sequence, and the differences $x_{n+1} - x_n$ are not bounded, then the language $\{a^{x_n}\}$ is not regular.

That covers lots of problems that you will find in a course, like your n!, or $a^p$ where p is prime, or $a^{n^2}$, or any infinite subsequence of such sequences.

Someone else asked about the language $\{0^{2^n}\}$. Same solution.

$\endgroup$

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.