Лемма о разрастании языка

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

Пример Язык L ₁ = { a^mbⁿ | m, n ³0} – регулярный, т.к., например, в строке aabbb повторение любой подстроки, образованной только из нулей или единиц, порождает строки (aaaabbb, aaabbb, aabbbb, aabbbbbb и т.д.) языка L ₁.

Язык L ₂ = { aⁿbⁿ | n ³1} – не регулярный, т.к. Действительно, любая итерация подстроки, состоящей только из нулей или единиц, нарушает баланс нулей и единиц. Подобные действия со смешанными подстроками, содержащими нули и единицы, приводят к нарушению порядка следования нулей и единиц. Таким образом, для языка L ₂ не строк, удовлетворяющих условиям леммы.

Удобным средством формального определения регулярных языков являются регулярные выражения.

Определение Регулярные выражения над алфавитом S определяются следующим образом:

1) Æ - регулярное выражение (обозначает пустоте регулярное множество Æ);

2) e - регулярное выражение (обозначает регулярное множество {e}, состоящее из пустой строки);

3) а ÎS - регулярное выражение (обозначает множество { а });

4) если p и q – регулярные выражения, обозначающие множества P и Q, то посредством операций над выражениями определяются выражения следующих трех типов:

а) p | q или p + q – регулярное выражение (обозначает объединение P È Q), где символ | или + называют операцией или (альтернативы);

б) pq или p × q – регулярное выражение (обозначает множество PQ = { xy | x Î P, y Î Q }), где символ «точка» (возможно умалчиваемый) называют операцией сцепления (конкатенации);

в) p ^* - регулярное выражение (обозначает множество P ^*), где символ «*» называют операцией итерации.

Соотношение между регулярными языками и регулярными выражениями устанавливает теорема Клини.

Теорема Клини. Каждому регулярному языку из S^* соответствует регулярное выражение над множеством S.

Пример Примеры регулярных выражений и их значений представлены в таблице 2.1.

Таблица 2.1 – Примеры регулярных выражений

В практических приложениях вводятся дополнительные соглашения относительно записи регулярных выражений, например, запись вида р ⁺ используется для обозначения выражения рр ^*.