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

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

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

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

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

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

Теорема:

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

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

[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]

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

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

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

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

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

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

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

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

Регулярный язык [math]L_{1}[/math] входит (включается) в регулярный язык [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].

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

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

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

Теорема:

Детерминированный конечный автомат [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 (рус.)