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

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

ПримерЯзык 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 – Примеры регулярных выражений

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

Конечные автоматы