Вопрос

I am struggling to prove the following question.

$L_1 = \{a^n: n \text{ is a product of exactly two primes}\}$

I feel like the language is not regular but I am having trouble proving it. I tried using pumping lemma but got stuck at the end. Here's how I did it:

Assume that the language is regular and $m$ is a constant of Pumping Lemma. Now let $w = a^M$ where $M > m$ and $M$ is a co-prime number. Clearly $w$ is in the language and $|w| > m$.

Now let $y=a^j$ where $j$ is between $1$ and $m$, with $|xy| \leq m$ and $|y| \geq 1$.

This is where I am getting stuck. I feel like we should pump up but I don't know by "how much". Also, I feel like I have to know what is the next co-prime number after $M$, but can't figure it out.

Нет правильного решения

Лицензировано под: CC-BY-SA с атрибуция
Не связан с cs.stackexchange
scroll top