Являются {a^n | n >= 0} и {a^p | р = простое число} не регулярно?

Question

В курсе CS у меня есть следующие примеры: {a^n | n >= 0} а также {a^p | p = prime number}

Эти языки регулярны или нет? Есть ли кто-нибудь, кто может сделать противоречие накачки леммы?

Answer 1

Как сказал Гарольд. Этот пример

а ^ п | п>=0

это обычный язык, это *.

Второй пример

{a^p | p = простое число}

Как гласит прокачивающая лемма, N = p -> наше слово будет ^ N. Итак, по определению |uv|=0) и v=a^s (s>=1). Остальной мир будет нашим w = a ^ (Nps). Определение говорит, что uv ^ m w (m>=0) должно быть на языке. Мы можем выбрать m = N + 1.

u * v ^ (N + 1)w = a ^ p a ^ (s * (N + 1)) * a ^ Nps = a^N(S+1)

Существует конфликт, потому что ^ N (S + 1) не является простым (потому что делитель, конечно, S+1), поэтому этот язык не является регулярным.