В курсе CS, который я беру, есть пример языка, который не является регулярным:
{a^nb^n | n >= 0}
Я могу понять, что он не является регулярным, так как не может быть записано Finite State Automaton/Machine, которое проверяет и принимает этот вход, поскольку в нем отсутствует компонент памяти. (Пожалуйста, поправьте меня, если я ошибаюсь)
запись в википедии на обычном языке также содержит этот пример, но не дает (математического) доказательства, почему оно не является регулярным.
Может ли кто-нибудь просветить меня по этому поводу и предоставить доказательство этому, или указать мне слишком хороший ресурс?
То, что вы ищете, Лекция по откачке для обычных языков.
Ниже приведен пример с вашей конкретной проблемой:
Примеры:
Пусть L = {a m b m | m ≥ 1}.
Тогда L не является регулярным. Доказательство. Пусть n такое же, как в лемме о накачке. Пусть w = a n b n.
Пусть w = xyz, как в лемме о накачке. Таким образом, xy 2 z ∈ L, однако xy 2 z содержит больше, чем bs.
Потому что вы не можете написать конечный автомат, который будет "считать" идентичные последовательности символов "a" и "b". В двух словах FSM не могут "подсчитать". Попробуйте представить такой FSM: сколько состояний вы бы дали символу "a"? Сколько до "б"? Что делать, если ваша последовательность ввода больше?
Обратите внимание, что если у вас было n <= X с X целочисленным значением, вы могли бы подготовить такой FSM (имея один с большим количеством состояний, но все же конечное число); такой язык будет регулярным.
Конечный автомат не имеет структуры данных (стека) - памяти, как в случае push down automaton. Да, это может дать вам некоторые "а затем некоторые" b, но не точное количество "a", за которым следует "b".