Анализ свойств регулярных языков (пустота, совпадение, включение, конечность, подсчёт числа слов)

Для различных операций с регулярными языками полезно знать некоторые их свойства. Как правило, в доказательствах этих свойств используется факт из теоремы Клини об эквивалентности автоматных и регулярных языков.

Пустота регулярного языка

Определение:

Регулярный язык называется пустым (англ. empty), если он не содержит ни одного слова.

Определение:

Регулярный язык содержащий хотя бы одно слово, называется непустым (англ. nonempty).

Теорема:

Регулярный язык является непустым тогда и только тогда, когда в любом задающем его автомате существует путь из стартового состояния в какое-либо из терминальных.

Доказательство:

[math]\triangleright[/math]

[math]\Rightarrow[/math] Пусть язык содержит слово [math]w[/math]. Любой детерминированный конечный автомат [math]A[/math], задающий этот язык, должен допускать [math]w[/math]. Тогда при переходе из стартового состояния [math]A[/math] по символам [math]w[/math] получится путь, оканчивающийся в одном из терминальных состояний. [math]\Leftarrow[/math] Пусть в автомате существует путь из стартового состояния в одно из допускающих. Рассмотрим последовательность символов на переходах, образующих этот путь. Строка из этой последовательности допускается автоматом, а значит, принадлежит языку.

[math]\triangleleft[/math]

Алгоритм проверки языка на пустоту

Для определения пустоты языка по соответствующему ему автомату проще всего использовать алгоритм обхода в глубину. Язык не является пустым тогда и только тогда, когда при поиске из стартового состояния автомата окажется достижимой хотя бы одна терминальная вершина.

Совпадение регулярных языков

Определение:

Два регулярных языка совпадают (англ. coincide), если любое слово или содержится в обоих языках, или не содержится ни в одном из них.

Для проверки совпадения языков достаточно запустить алгоритм проверки эквивалентности задающих их автоматов.

Пример проверки на совпадение регулярных языков

Для того, чтобы узнать равен ли язык своему замыканию Клини, нужно проверить на эквивалентность автомат, задающий язык, и автомат, задающий замыкание Клини языка. Если автоматы эквивалентны, то язык равен своему замыканию Клини.

Включение одного регулярного языка в другой

Определение:

Регулярный язык [math]L_{1}[/math] входит (включается) (англ. included) в регулярный язык [math]L_{2}[/math], если любое слово, принадлежащее [math]L_{1}[/math], принадлежит [math]L_{2}[/math].

Пусть автомат [math]M_1[/math] задаёт язык [math]L_1[/math], а автомат [math]M_2[/math] — язык [math]L_1 \cap L_2[/math]. Для проверки включения [math]L_1[/math] в [math]L_2[/math] достаточно проверить эквивалентность [math]M_1[/math] и [math]M_2[/math].

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

Определение:

Регулярный язык называется конечным (англ. finite), если принадлежащее ему множество слов конечно.

Теорема:

Детерминированный конечный автомат [math]A_{1}[/math] задаёт конечный язык тогда и только тогда, когда в [math]A_{1}[/math] не существует состояния [math]v[/math], для которого выполняются три условия: [math]v[/math] достижимо из стартового состояния [math]s[/math]; из [math]v[/math] достижимо какое-либо из допускающих состояний; из [math]v[/math] по одному или более переходам достижимо [math]v[/math].

Доказательство:

[math]\triangleright[/math]

Пусть такое состояние [math]v[/math] существует, а строки [math]x, y, z[/math] таковы, что [math]\langle s, xyz \rangle \vdash ^{*} \langle v, yz \rangle \vdash ^{*} \langle v, z \rangle \vdash ^{*} \langle t, \epsilon \rangle[/math], [math]t[/math] — допускающее, [math]y[/math] — непустая. Рассмотрим строки вида [math]xy^{k}z, k \in \mathbb{N}[/math]. Их бесконечное количество, и все они, как легко увидеть, допускаются автоматом. Значит, язык бесконечен. Пусть такого состояния не существует. Тогда любой путь из стартового состояния в какое-либо из допускающих является простым. Количество слов в языке равно количеству таких путей; количество путей, в свою очередь, ограничено [math]n! | \Sigma |^{n-1}[/math], где [math]n[/math] — количество состояний автомата: [math]n![/math] — количество перестановок состояний, [math]| \Sigma |^{n-1}[/math] — количество совокупностей переходов по символам между ними. Таким образом, язык конечен.

[math]\triangleleft[/math]

Алгоритм нахождения числа слов в языке

Доказанное утверждение позволяет свести задачу поиска числа слов в языке к поиску количества различных путей в ациклическом графе. Сначала с помощью обхода в глубину по обратным рёбрам определим полезные состояния, из которых достижимо хотя бы одно допускающее. Затем найдём любой цикл, состояния которого полезны, достижимый из старта; при нахождении констатируем бесконечность языка. Пусть язык конечен; тогда отсортируем автомат топологически. Введём функцию [math]\mathrm{paths} (v)[/math], задающую число различных путей из [math]s[/math] в [math]v[/math]; [math]\mathrm{paths} (s) = 1[/math]. Заметим, что если известны значения [math]\mathrm{paths} (u)[/math] для всех [math]u[/math], из которых существует переход в [math]v[/math], то [math]\mathrm{paths} (v) = \sum\limits_{u}\mathrm{paths} (u)[/math]. Количеством слов в языке будет сумма [math]\mathrm{paths} (t)[/math] для всех допускающих [math]t[/math].

См. также

• Замкнутость регулярных языков относительно различных операций
• Теорема Клини (совпадение классов автоматных и регулярных языков)
• Доказательство нерегулярности языков: лемма о разрастании

Источики информации

• Хопкрофт Д., Мотвани Р., Ульман Д. — Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. — Москва: Издательский дом «Вильямс», 2002. — с. 169-177 — ISBN 5-8459-0261-4