Почему {a ^ nb ^ n | n> = 0} не регулярно?

Question

В курсе CS, который я беру, есть пример языка, который не является регулярным:

{a^nb^n | n >= 0}

Я могу понять, что это не регулярно, поскольку не может быть написан конечный автомат / машина, которая проверяет и принимает этот ввод, так как в нем отсутствует компонент памяти. (Пожалуйста, поправьте меня, если я ошибаюсь)

Запись в Википедии о регулярном языке также перечисляет этот пример, но не предоставляет (математического) доказательства, почему он не является регулярным.

Может ли кто-нибудь просветить меня в этом и предоставить доказательства этого или указать мне слишком хороший ресурс?

Answer 1

То, что вы ищете, это Насосная лемма для обычных языков .

Вот пример с вашей точной проблемой:

Примеры:
Пусть L = {a ^m b ^m | m ≥ 1}.
Тогда L не является регулярным.
Доказательство: пусть n будет таким же, как в лемме прокачки.
Пусть w = a ⁿ b ⁿ .
Пусть w = xyz, как в лемме о накачке.
Таким образом, xy ² z ∈ L, однако xy ² z содержит больше а, чем b.

Answer 2

Поскольку вы не можете написать конечный автомат, который будет «считать» идентичные последовательности символов «a» и «b». Короче говоря, ФСМ не могут «сосчитать». Попробуйте представить себе такого автомата: сколько штатов вы бы дали символу «а»? Сколько нужно «б»? Что если в вашей входной последовательности больше?

Обратите внимание, что если бы у вас было n <= X с целочисленным значением X, вы могли бы подготовить такой FSM (имея одно с большим количеством состояний, но все же конечное число); такой язык будет регулярным. </p>

Answer 3

Конечное состояние Автомат не имеет структуры данных (стека) - памяти, как в случае с автоматом нажатия. Да, это может дать вам несколько «а», затем несколько «б», но не точное количество «а», за которым следует «нет».