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

Вы ищете лемму о перекачке для обычных языков.

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

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

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

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

Причина в том, что вы должны достичь конечного состояния только тогда, когда нет. из «а» и нет. из 'b' во входной строке равны. А для этого нужно посчитать и то, и другое - нет. как "а", так и "нет". из 'b', но поскольку значение 'n' может достигать бесконечности, невозможно считать до бесконечности с помощью конечных автоматов.

Так вот почему {a ^ n b ^ n | n> = 0} не является регулярным.

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

Предположим, L = {a ⁿ b ⁿ | n ≥ 0} является регулярным. Тогда мы можем воспользоваться леммой о накачке.

Пусть n номер леммы о накачке. Рассмотрим w = a ⁿ b ⁿ ∈L. Лемма о накачке утверждает, что вы можете разделить w на xyz так, чтобы xy ≤ n, y ≥ 1 и < strong> ∀ i∈ℕ ₀: xy ⁱ z∈L.

Используя первые два правила, мы легко видим, что независимо от того, как мы делим w на xyz, y всегда будет состоять только из a s и что он будет содержать хотя бы одну такую ​​букву. С помощью правила 3 ​​заключаем, что a ^n-k b ⁿ ∈L, где k = | y | ≥ 1. Но nk ≠ n нарушает определение L, поэтому a ^nk b ⁿ ∉L < / сильный>. Получили противоречие ????, и мы заключаем, что предположение о регулярности L неверно.