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

Question

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

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

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

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

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

Answer 1

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

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

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

Answer 2

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

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

Answer 3

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

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

Answer 4

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

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

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

Answer 5

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

Answer 6

Лемму о накачке можно использовать для опровержения того, что язык не является регулярным,

Пример:

Пусть L = {a^mb^m | м ≥ 1}

Тогда L не является регулярным.

Доказательство. Предположим, что L регулярно.

Пусть n такое же, как в лемме о накачке.

Пусть w = a^nb^n.

Пусть w = xyz соответствует лемме о накачке.

Теперь y содержит только 'a', так как |xy|<= n и i = 2 (в xy^iz).

Таким образом, xy^2z ∈ L, однако xy^2z содержит больше a, чем b.

Что противоречит первому предположению, поэтому оно не является регулярным.

Answer 7

Поясню здесь на примере:

L = {а^nb^n | п >= 0};

Строка минимальной длины, принятая в L:

{ε, ab, aabb, ...} => минимум w = ab;

не брал, так как для n == 0, никогда не может быть.

давайте сначала возьмем x = ε, тогда и z = bили и , так как |y| > 0а также |xy| <= 2(поскольку это бесконечный язык, p(здесь 2) может быть максимальной длины ссылки на строку здесь )

после откачки y = a:

L' = ааб, аааб, ааааб, аааааб;

после откачки y = ab:

L' = абаб, абабаб, абабаб;

Теперь возьми x = a, тогда и z = ε; после откачки y = b:

L' = абб, аббб, аббб, абббб;

Снова проверьте w = aabb : w находится в L;

за xможет быть ε, a, aa, aab, то может быть a, aa, bb, ab, aab, ... aabbа также zможет быть ε, b, bb, abb;

Во всех приведенных выше случаях после прокачки любой длины yне будет принято в L. L'либо имеет неравные a, b, либо порядок не соответствует определению. Следовательно L = {a^n.b^n | n >= 0};не является регулярным, так как не соответствует лемме о накачке для регулярных языков .