Мы можем выписать некоторые из самых коротких строк в языке, чтобы почувствовать это:
S -> aTb -> ab
S -> aTb -> aabb
S -> SS -> … -> abab
S -> SS -> … -> abaabb
S -> SS -> … -> aabbab
Мы отмечаем, что единственные строки, генерируемые грамматикой, принимают каждый экземпляр S для либо ab, либо aabb. Кроме того, мы можем получить любое количество S в наших промежуточных формах, используя S -> SS. Следовательно, это обычный язык (ab + aabb)+.
Доказательством является индукция по длине строки n.
Базовый случай: самые короткие строки ab и aabb находятся на языке (ab + aabb)+ и генерируются грамматикой, как показано выше.
Гипотеза индукции: язык, генерируемый грамматикой, соответствует языку (ab + aabb)+ для всех строк вплоть до длины k.
Шаг индукции: мы должен показать, что строки, сгенерированные грамматикой следующей наибольшей длины, находятся на языке, а строки на языке следующей наибольшей длины сгенерированы грамматикой. Примечание: грамматика может генерировать только строки четной длины, а язык (ab + aabb)+ содержит только строки четной длины, так что на самом деле следующий самый высокий шаг - это наименьшее четное число, большее k.
Мы знаем язык и соответствие грамматики для строк длиной k. Пусть X будет множеством всех строк на языке длины k, а Y будет множеством всех строк на языке длины k - 2. Затем грамматика генерирует множество строк X ', модифицируя производные строк в X использовал производство S -> SS один раз, а затем выбрал S -> aTb -> ab для этого экземпляра S, который только что появился. Грамматика также генерирует набор строк Y ', модифицируя производные строк в Y, чтобы использовать производство S -> SS один раз, а затем выбирая S -> aTb -> aabb для этого только что введенного экземпляра S. Эти же строки соответствуют регулярному выражению, поскольку строки в X и Y совпадают, а X 'и Y' - это только те строки с добавленным ab или aabb, что допускается звездой Клини.
Аналогично К строкам длины k и k-2, которые соответствуют регулярному выражению, в конец можно добавить или ab, или aabb (благодаря звезде Клини), чтобы получить все совпадающие строки длины k + 2. Но они также должны быть сгенерированы грамматикой, поскольку префиксы были сгенерированы грамматикой, и у нас есть произведения (описанные выше), которые позволяют нам вводить дополнительные ab или aabb в наши производные строки.
На словах язык - это набор всех строк, которые являются конкатенациями любого числа экземпляров строк ab и aabb в любом порядке.