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

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

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

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

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

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

Ответ 1

То, что вы ищете, Лекция по откачке для обычных языков.

Ниже приведен пример с вашей конкретной проблемой:

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

Ответ 2

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

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

Ответ 3

Конечный автомат не имеет структуры данных (стека) - памяти, как в случае push down automaton. Да, это может дать вам некоторые "а затем некоторые" b, но не точное количество "a", за которым следует "b".