1

I am having trouble proving the irregularity of the following language:

$L_2 = \{a^n | n \text{ is not a prime}\}$

I understand that since regular languages are closed under complementation, L_2 isn't regular if it's complement isn't regular. I'm not sure how to proceed further with this problem though.

Any help would be greatly appreciated!

Christopher Liu
  • 1,319
user149379
  • 13

1 Answers1

0

So we see easily that $L_2$ is just the complement of the language $\{a^n|n \text{ is a prime}\}$. A language is regular iff its complement is regular.

Suppose that the complement is regular, then you have a machine $M$ with finitely many states, say, $k$ that accepts this language. So, by the pigeonhole principle, you can put in $a^{n_1}, a^{n_2}, \ldots, a^{n_k}$ where $n_i$ are prime and at least two of these $a^{n_i}$s end up on the same accept state. Can you take it from here?

Christopher Liu
  • 1,319