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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
Строка 76: Строка 76:
 
=== Алгоритм нахождения числа слов в языке ===
 
=== Алгоритм нахождения числа слов в языке ===
  
Доказанное утверждение позволяет свести задачу поиска числа слов в языке к поиску количества различных путей в ациклическом графе. Сначала с помощью [[Обход в глубину, цвета вершин|обхода в глубину]] по обратным рёбрам определим '''полезные''' состояния, из которых достижимо хотя бы одно допускающее. Затем найдём любой цикл, состояния которого полезны, достижимый из старта; при нахождении констатируем бесконечность языка. Пусть язык конечен; тогда отсортируем автомат [[Использование обхода в глубину для топологической сортировки|топологически]]. Введём функцию <tex>paths(v)</tex>, задающую число различных путей из <tex>s</tex> в <tex>v</tex>; <tex>paths(s) = 1</tex>. Заметим, что если известны значения <tex>paths(u)</tex> для всех <tex>u</tex>, из которых существует переход в <tex>v</tex>, то <tex>paths(v) = \sum\limits_{u}paths(u)</tex>. Количеством слов в языке будет сумма <tex>paths(t)</tex> для всех допускающих <tex>t</tex>.
+
Доказанное утверждение позволяет свести задачу поиска числа слов в языке к поиску количества различных путей в ациклическом графе. Сначала с помощью [[Обход в глубину, цвета вершин|обхода в глубину]] по обратным рёбрам определим '''полезные''' состояния, из которых достижимо хотя бы одно допускающее. Затем найдём любой цикл, состояния которого полезны, достижимый из старта; при нахождении констатируем бесконечность языка. Пусть язык конечен; тогда отсортируем автомат [[Использование обхода в глубину для топологической сортировки|топологически]]. Введём функцию <tex>\mathrm{paths} (v)</tex>, задающую число различных путей из <tex>s</tex> в <tex>v</tex>; <tex>\mathrm{paths} (s) = 1</tex>. Заметим, что если известны значения <tex>\mathrm{paths} (u)</tex> для всех <tex>u</tex>, из которых существует переход в <tex>v</tex>, то <tex>\mathrm{paths} (v) = \sum\limits_{u}\mathrm{paths} (u)</tex>. Количеством слов в языке будет сумма <tex>\mathrm{paths} (t)</tex> для всех допускающих <tex>t</tex>.
  
 
== Литература ==
 
== Литература ==

Версия 17:12, 12 декабря 2013

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

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

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


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

Теорема:
Регулярный язык является непустым тогда и только тогда, когда в любом задающем его автомате существует путь из стартового состояния в какое-либо из терминальных.
Доказательство:
[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 (рус.)


Примечания