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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Пример)
(Пример)
Строка 20: Строка 20:
  
 
== Пример ==
 
== Пример ==
 +
=== Система уравнений ===
 
[[Файл:at_least_one_zero.png|right]]
 
[[Файл:at_least_one_zero.png|right]]
 
Найдем регулярное выражение для языка двоичных представлений чисел, в которых есть хотя бы один ноль
 
Найдем регулярное выражение для языка двоичных представлений чисел, в которых есть хотя бы один ноль
Строка 41: Строка 42:
  
 
Откуда <tex>L_2 = 01^* (0 + 1)^*</tex>.
 
Откуда <tex>L_2 = 01^* (0 + 1)^*</tex>.
 +
 +
=== Обычный вариант ===
  
 
Теперь найдем регулярное выражение для этого же автомата с помощью теоремы Клини (обычный вариант).
 
Теперь найдем регулярное выражение для этого же автомата с помощью теоремы Клини (обычный вариант).

Версия 21:40, 3 января 2017

Альтернативное доказательство

Теорема:
Класс автоматных языков является подмножеством регулярных.
Доказательство:
[math]\triangleright[/math]
Автомат1.png

Рассмотрим автоматный язык [math]L[/math] и ДКА для него. Для доказательства теоремы достаточно построить регулярное выражение, порождающее язык [math]L[/math].

Пусть наш автомат состоит из [math]n[/math] состояний, и состояние [math]0[/math] — стартовое. Также пусть [math]L_i[/math] — язык, состоящий из слов, которые приводят из состояния [math]i[/math] в терминальное.

Заметим, что [math]L_i = \bigcup c L_j[/math] для всех [math] c \in \Sigma [/math] и [math]j[/math] таких, что [math]\delta(i, c)=j[/math]. Действительно, если по слову [math] \alpha [/math] из состояния [math]j[/math] мы можем попасть в терминальное состояние, а между состояниями [math] i [/math] и [math] j [/math] есть переход по символу [math] c [/math], то слово [math] c \alpha [/math] принадлежит языку [math]L_i[/math]. Также, если [math]\varepsilon \in L_i[/math], то есть если состояние является терминальным, то добавим [math]\varepsilon[/math] в объединение для [math]L_i[/math].

Мы получили систему из [math]n[/math] регулярных выражений с [math]n[/math] неизвестными, причем [math] \varepsilon \notin \alpha_{ij}[/math] ([math] \alpha_{ij} [/math] — коэффициент перед [math] j [/math]-й переменной в [math] i [/math] уравнении) для всех [math] i [/math] и [math] j [/math], так как в автомате нет [math] \varepsilon [/math]-переходов, а следовательно, система имеет единственное решение. Также заметим, что [math]L_0[/math] содержит все слова, по которым из стартового состояния можно дойти до терминального, но тогда [math]L_0 = L[/math].

В итоге мы построили систему уравнений в регулярных выражениях, решив которую, мы получим регулярное выражение, порождающее язык [math]L[/math].
[math]\triangleleft[/math]

Отметим, что длина построенного таким образом регулярного выражения обычно заметно короче, чем если бы мы строили его по теореме Клини.

Пример

Система уравнений

At least one zero.png

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

[math] \begin{cases} L_1 = 1L_1\\ L_2 = 0L_1 + 0L_2 + 1L_2 + \varepsilon \end{cases} [/math]

Найдем [math] L_1 [/math]:

[math]L_1 = 1L_1[/math].

Так как [math] \varepsilon \notin 1 [/math], то [math]L_1 = 1^*[/math].

Выразим [math] L_2 [/math] через [math] L_1 [/math]:

[math]L_2 = 0L_1 + 0L_2 + 1L_2 + \varepsilon[/math]

Откуда [math]L_2 = 01^* (0 + 1)^*[/math].

Обычный вариант

Теперь найдем регулярное выражение для этого же автомата с помощью теоремы Клини (обычный вариант). Для начала построим таблицу, согласно теореме по шагам:

Выражение Значения
[math]R_{11}^{(0)}[/math] [math]\varepsilon + 1[/math]
[math]R_{12}^{(0)}[/math] [math]0[/math]
[math]R_{21}^{(0)}[/math] [math]\varnothing[/math]
[math]R_{22}^{(0)}[/math] [math](\varepsilon + 0 + 1)[/math]

Например, в выражении [math]R_{11}^{(0)}[/math] присутствует член [math]\varepsilon[/math], потому что и начальным, и конечным является состояние [math]1[/math]. Это выражение включает также [math]1[/math], поскольку существует путь из состояния [math]1[/math] в состояние [math]1[/math] по входу [math]1[/math]. Выражение [math]R_{12}^{(0)}[/math] равно [math]0[/math], потому что есть дуга с меткой [math]0[/math], ведущая из состояния [math]1[/math] в состояние [math]2[/math]. Здесь нет члена [math]\varepsilon[/math], поскольку начальное и конечное состояния различаются. И, наконец, [math]R_{21}^{(0)} = \varnothing[/math], так как нет путей, ведущих из состояния [math]2[/math] в состояние [math]1[/math]. Теперь применим индукцию для построения более сложных выражений.

Правило для вычисления выражения [math]R_{ij}^{(1)}[/math] представляет собой пример общего правила из части теоремы Клини:

[math]R_{ij}^{(1)} = R_{ij}^{(0)} + R_{i1}^{(0)} (R_{11}^{(0)})^* R_{1j}^{(0)}[/math]

Выражение Прямая подстановка Упрощенное выражение
[math]R_{11}^{(1)}[/math] [math]\varepsilon + 1 + (\varepsilon + 1)(\varepsilon + 1)^*(\varepsilon + 1)[/math] [math]1^*[/math]
[math]R_{12}^{(1)}[/math] [math]0 + (\varepsilon + 1)(\varepsilon + 1)^*0[/math] [math]1^*0[/math]
[math]R_{21}^{(1)}[/math] [math]\varnothing + \varnothing(\varepsilon + 1)^*(\varepsilon + 1)[/math] [math]\varnothing[/math]
[math]R_{22}^{(1)}[/math] [math]\varepsilon + 0 + 1 + \varnothing(\varepsilon + 1)^*0[/math] [math](\varepsilon + 0 + 1)[/math]

И, наконец, последний шаг индукции

Выражение Упрощенное выражение (после подстановки)
[math]R_{11}^{(1)}[/math] [math]1^*[/math]
[math]R_{12}^{(1)}[/math] [math]1^*0(0 + 1)^*[/math]
[math]R_{21}^{(1)}[/math] [math]\varnothing[/math]
[math]R_{22}^{(1)}[/math] [math](0 + 1)^*[/math]

Окончательное регулярное выражение, эквивалентное автомату, строится путем объединения всех тех выражений, для которых первое состояние является начальным, а второе — заключительным. В нашем примере [math]1[/math] — начальное состояние, а [math]2[/math] — заключительное, поэтому нам нужно лишь выражение [math]R_{12}^{(1)}[/math], равное [math]1^*0(0 + 1)^*[/math]

См. также

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