Дальнейшие свойства регулярных языков и признаки нерегулярности языков

Лекция 7.ДАЛЬНЕЙШИЕ СВОЙСТВА РЕГУЛЯРНЫХ ЯЗЫКОВ И ПРИЗНАКИ НЕРЕГУЛЯРНОСТИ ЯЗЫКОВ Итак, мы установили совпадение трех классов: автоматных языков, регулярных множеств и регулярных языков, а это означает эквивалентность всех трех определений и позволяет использовать то или иное определение класса регулярных языков в зависимости от конкретной задачи. Но этот результат дает повод задать вопрос: нельзя ли из регулярных языков с помощью обычных теоретико-множественных операций и некоторых других (таких, как катенация, итерация) получить языки, не являющиеся регулярными? Последний вопрос относится к свойствам алгебраической замкнутости класса регулярных языков. Другие вопросы связаны с существованием алгоритмов, позволяющих определять те или иные свойства языков, например, конечен язык или бесконечен. Мы убедимся, что в классе регулярных языков для целого ряда важных случаев удается найти положительный ответ на вопрос о существовании алгоритма. И наконец, еще один принципиальный вопрос: можно ли по данному языку определить, регулярен он или нет? Если язык регулярен, можно попытаться построить для него ДКА, найти регулярное выражение или регулярную грамматику. Но если язык не является регулярным, то потребуется найти способ обоснования факта нерегулярности. В частности, если указав некоторые полезные необходимые условия, которым удовлетворяют все регулярные языки, можно показать, что данный язык не подчиняется этим условиям. Тогда рассматриваемый язык, очевидно, не будет регулярным. Такие условия содержит Лемма о накачке для регулярных языков. Следующий результат, известный как Лемма о накачке для регулярных языков (Pumping Lemma) основан на том простом замечании, что в диаграмме переходов с n вершинами любой путь длины, большей или равной n, должен содержать цикл, т.е. повторяющуюся вершину. Теорема. (Лемма о накачке для регулярных языков) Пусть L – регулярный язык. Тогда существует целое число m > 0 такое, что для любой строки L, длина которой m, возможно представление = где 0и , m, такое, что для любого i = 0, 1, 2, ... строка i = i также принадлежит L. Доказательство. Если язык L регулярный, тогда существует ДКА M, который распознает его. Пусть q0, q1, ..., qn – множество всех состояний автомата M. Возьмем любую строку L такую, что =k m = n+1. Если язык L бесконечен, то такая достаточно длинная строка всегда найдется. Рассмотрим все те состояния автомата M, через которые он проходит, когда прочитывает строку ; пусть это будут состояния q0, qi, qj, ..., qf. Так как эта последовательность имеет k + 1 вершину и k + 1 > n + 1, то, по крайней мере, одна вершина должна повториться, по крайней мере, на n-м шаге. Таким образом, указанная последовательность имеет следующий вид: q0, qi, qj, ..., qr, ..., qr, ..., qf . причем, можно считать, что в последовательности q0, qi, qj, ..., qr ,…, qr уже нет других повторяющихся элементов, кроме последнего qr . Но тогда должны существовать подстроки , , строки *(q0, ) = qr, *(qr, ) = qr, *(qr, ) = qf, такие, что причем n+1 = m и 1. Отсюда непосредственно получаем, что *(q0, ) = qf, а также *(q0, 2 ) = qf, *(q0, 3 ) = qf. Это завершает доказательство леммы о накачке. Следует заметить, что лемма о накачке применима только к бесконечным языкам, ибо любая достаточно длинная строка языка после «накачки» приводит к порождению бесконечной последовательности строк этого же языка. Все конечные языки заведомо регулярны, но среди слов в них нет таких, чтобы их длина была больше, чем длина накачки. Лемма о накачке чаще всего применяется для доказательства того, что какой-то бесконечный язык не является регулярным. Такое доказательство проводится методом "от противного" с целью получить противоречие. Но, как и любое другое необходимое условие, Лемма о накачке не может использоваться для доказательства регулярности какого-то языка. Пример 1. Показать, используя Лемму о накачке, что язык L = {an bn n 0} не является регулярным. Допустим противное, т.е. что язык L – регулярный. Тогда к L применима Лемма о накачке, а значит, и должно существовать такое m-длина накачки языка, что если факторизованном виде = n > m, где . Для строки возможны три случая: 1) = аk, 2) = bt, 3) = akbt. В каждом из этих случаев мы получаем: L, то можно представить в 1) i = an - k (ak)i bn, 2) i = an (bt)i bn - t, 3) i = an - k (akbt)i bn - t. Полагая i = 2, убеждаемся, что ни в одном из случаев 2 не принадлежит L, что противоречит утверждению Леммы о накачке. Следовательно, первоначальное предположение о регулярности языка L неверно, т.е. язык {anbn n 0} не является регулярным. Пример 2. Показать, что язык L = {anbm n m, n 0, m 0} не является регулярным. Можно и здесь попытаться прямо использовать Лемму о накачке, но мы дадим другое решение, опирающееся на предыдущий пример. Допустим, что L – регулярный язык. Тогда регулярным должен быть и язык L1 = Но L1 = {an bn n L(a* b*). 0} и, как уже было показано, не является регулярным. Следовательно, и L не может быть регулярным.