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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Пример: исправлена бага в примере)
(Обычный вариант)
 
(не показано 13 промежуточных версий 2 участников)
Строка 8: Строка 8:
 
Рассмотрим автоматный язык <tex>L</tex> и ДКА для него. Для доказательства теоремы достаточно построить регулярное выражение, порождающее язык <tex>L</tex>.
 
Рассмотрим автоматный язык <tex>L</tex> и ДКА для него. Для доказательства теоремы достаточно построить регулярное выражение, порождающее язык <tex>L</tex>.
  
Пусть наш автомат состоит из <tex>n</tex> состояний, и состояние <tex>0</tex> {{---}} стартовое. Также пусть <tex>L_i</tex> {{---}} язык, состоящий из слов, которые приводят из состояния <tex>i</tex> в терминальное.
+
Пусть наш автомат состоит из <tex>n</tex> состояний, и состояние <tex>0</tex> стартовое. Также пусть <tex>L_i</tex> язык, состоящий из слов, которые приводят из состояния <tex>i</tex> в терминальное.
  
Заметим, что <tex>L_i = \sum c L_j</tex> для всех <tex> c \in \Sigma </tex> и <tex>j</tex> таких, что <tex>\delta(i, c)=j</tex>. Действительно, если по слову <tex> \alpha </tex> из состояния <tex>j</tex> мы можем попасть в терминальное состояние, а между состояниями <tex> i </tex> и <tex> j </tex> есть переход по символу <tex> c </tex>, то слово <tex> c \alpha </tex> принаджелит языку <tex>L_i</tex>. Также, если <tex>\varepsilon \in L_i</tex>, то есть, если состояние является терминальным, то добавим <tex>\varepsilon</tex> в сумму для <tex>L_i</tex>.
+
Заметим, что <tex>L_i = \bigcup c L_j</tex> для всех <tex> c \in \Sigma </tex> и <tex>j</tex> таких, что <tex>\delta(i, c)=j</tex>. Действительно, если по слову <tex> \alpha </tex> из состояния <tex>j</tex> мы можем попасть в терминальное состояние, а между состояниями <tex> i </tex> и <tex> j </tex> есть переход по символу <tex> c </tex>, то слово <tex> c \alpha </tex> принадлежит языку <tex>L_i</tex>. Также, если <tex>\varepsilon \in L_i</tex>, то есть если состояние является терминальным, то добавим <tex>\varepsilon</tex> в объединение для <tex>L_i</tex>.
  
Мы получили [[Решение уравнений в регулярных выражениях#Решение системы уравнений в регулярных выражениях | систему]] из <tex>n</tex> регулярных выражений с <tex>n</tex> неизвестными, причем <tex> \varepsilon \notin \alpha_{ij}</tex> (<tex> \alpha_{ij} </tex> {{---}} коэффициент перед <tex> j </tex>-й переменной в <tex> i </tex>-м [[Решение уравнений в регулярных выражениях#Решение системы уравнений в регулярных выражениях | уравнении]]) для всех <tex> i </tex> и <tex> j </tex>, так как в автомате нет <tex> \varepsilon </tex>-переходов, а, следовательно, система имеет единственное решение. Также заметим, что <tex>L_0</tex> содержит все слова, по которым из стартового состояния можно дойти до терминального, но тогда <tex>L_0 = L</tex>.
+
Мы получили [[Решение уравнений в регулярных выражениях#Решение системы уравнений в регулярных выражениях | систему]] из <tex>n</tex> регулярных выражений с <tex>n</tex> неизвестными, причем <tex> \varepsilon \notin \alpha_{ij}</tex> (<tex> \alpha_{ij} </tex> {{---}} коэффициент перед <tex> j </tex>-й переменной в <tex> i </tex>-м [[Решение уравнений в регулярных выражениях#Решение системы уравнений в регулярных выражениях | уравнении]]) для всех <tex> i </tex> и <tex> j </tex>, так как в автомате нет <tex> \varepsilon </tex>-переходов, а следовательно, система имеет единственное решение. Также заметим, что <tex>L_0</tex> содержит все слова, по которым из стартового состояния можно дойти до терминального, но тогда <tex>L_0 = L</tex>.
  
 
В итоге мы построили систему уравнений в регулярных выражениях, решив которую, мы получим регулярное выражение, порождающее язык <tex>L</tex>.
 
В итоге мы построили систему уравнений в регулярных выражениях, решив которую, мы получим регулярное выражение, порождающее язык <tex>L</tex>.
 
}}
 
}}
  
Отметим, что длина построенного таким образом регулярного выражения обычно заметно короче, чем если бы мы строили его по [[Теорема Клини (совпадение классов автоматных и регулярных языков) | теореме Клини]].
+
Отметим, что длина построенного таким образом регулярного выражения обычно заметно короче, чем если бы мы строили его по [[Теорема Клини (совпадение классов автоматных и регулярных языков) | теореме Клини]]. Кроме того, построение регулярного выражения таким образом обычно гораздо проще (выполняется за меньшее количество шагов).
  
 
== Пример ==
 
== Пример ==
[[file:Автомат2.png|450px|right]]
+
=== Система уравнений ===
Найдем регулярное выражение для языка двоичных представлений чисел кратных трем.
+
[[Файл:at_least_one_zero.png|right]]
 +
Найдем регулярное выражение для языка двоичных представлений чисел, в которых есть хотя бы один ноль. Для этого составим уравнение, добавляя соответствующие переменные в правую часть при наличии перехода по символу, а так же <tex>\varepsilon</tex> для терминального состояния, как это указано в доказательстве.  
  
 
<tex>
 
<tex>
 
\begin{cases}
 
\begin{cases}
L_0 = 0L_0+1L_1+\varepsilon \\
+
L_1 = 1L_1\\
L_1 = 1L_0+0L_2 \\
+
L_2 = 0L_1 + 0L_2 + 1L_2 + \varepsilon 
L_2 = 0L_1+1L_2
 
 
\end{cases}
 
\end{cases}
 
</tex>
 
</tex>
  
Выразим <tex>L_2</tex> из третьего уравнения, подставив <tex> L_1 </tex> из второго:
+
Найдем <tex> L_1 </tex>:
  
<tex>L_2 = (00 + 1)L_2+01L_0</tex>.
+
<tex>L_1 = 1L_1</tex>.
  
Так как <tex> \varepsilon \notin (00 + 1) </tex>, то <tex>L_2 = (00+1)^*01L_0</tex>.
+
Так как <tex> \varepsilon \notin 1 </tex>, то <tex>L_1 = 1^*</tex>.
  
Подставим <tex>L_2</tex> во второе уравнение, а потом получившееся выражение подставим в первое, чтобы найти <tex>L_0</tex>:
+
Выразим <tex> L_2 </tex> через <tex> L_1 </tex>:
  
<tex>L_0 = 0L_0 + 11L_0 + 10(00+1)^*01L_0 + \varepsilon </tex>.
+
<tex>L_2 = 0L_1 + 0L_2 + 1L_2 + \varepsilon</tex>
  
Решив уравнение, получим что <tex>(0 + 11 + 10(00+1)^*01)^*</tex> {{---}} регулярное выражение, порождающее искомый язык.
+
Откуда <tex>L_2 = 01^* (0 + 1)^*</tex>.
 +
 
 +
=== Обычный вариант ===
 +
 
 +
Теперь найдем регулярное выражение для этого же автомата с помощью теоремы Клини (обычный вариант).
 +
Для начала построим таблицу, согласно [[Теорема_Клини_(совпадение_классов_автоматных_и_регулярных_языков) | теореме]] по шагам:
 +
 
 +
{| border="1" class="wikitable" style="width: 250px; height: 250px; float: left;"
 +
!style="background:#41aef0"|Выражение
 +
!style="background:#41aef0"|Значения
 +
|-
 +
|<tex>R_{11}^{(0)}</tex>
 +
|<tex>\varepsilon + 1</tex>
 +
|-
 +
|<tex>R_{12}^{(0)}</tex>
 +
|<tex>0</tex>
 +
|-
 +
|<tex>R_{21}^{(0)}</tex>
 +
|<tex>\varnothing</tex>
 +
|-
 +
|<tex>R_{22}^{(0)}</tex>
 +
|<tex>(\varepsilon + 0 + 1)</tex>
 +
|}
 +
<div style="clear:both;"></div>
 +
 
 +
Например, в выражении <tex>R_{11}^{(0)}</tex> присутствует член <tex>\varepsilon</tex>, потому что и начальным, и конечным является состояние <tex>1</tex>. Это выражение включает также <tex>1</tex>, поскольку существует путь
 +
из состояния <tex>1</tex> в состояние <tex>1</tex> по входу <tex>1</tex>. Выражение <tex>R_{12}^{(0)}</tex> равно <tex>0</tex>, потому что есть дуга с
 +
меткой <tex>0</tex>, ведущая из состояния <tex>1</tex> в состояние <tex>2</tex>. Здесь нет члена <tex>\varepsilon</tex>, поскольку начальное
 +
и конечное состояния различаются. И, наконец, <tex>R_{21}^{(0)} = \varnothing</tex>, так как нет путей, ведущих из
 +
состояния <tex>2</tex> в состояние <tex>1</tex>.
 +
Теперь применим индукцию для построения более сложных выражений.
 +
 
 +
Правило для вычисления выражения <tex>R_{ij}^{(1)}</tex> представляет собой пример общего правила из части теоремы Клини:
 +
 
 +
<tex>R_{ij}^{(1)} = R_{ij}^{(0)} + R_{i1}^{(0)} (R_{11}^{(0)})^* R_{1j}^{(0)}</tex>
 +
 
 +
{| border="1" class="wikitable" style="width: 300px; height: 250px; float: left;"
 +
!style="background:#41aef0"|Выражение
 +
!style="background:#41aef0"|Прямая подстановка
 +
!style="background:#41aef0"|Упрощенное выражение
 +
|-
 +
|<tex>R_{11}^{(1)}</tex>
 +
|<tex>\varepsilon + 1 + (\varepsilon + 1)(\varepsilon + 1)^*(\varepsilon + 1)</tex>
 +
|<tex>1^*</tex>
 +
|-
 +
|<tex>R_{12}^{(1)}</tex>
 +
|<tex>0 + (\varepsilon + 1)(\varepsilon + 1)^*0</tex>
 +
|<tex>1^*0</tex>
 +
|-
 +
|<tex>R_{21}^{(1)}</tex>
 +
|<tex>\varnothing + \varnothing(\varepsilon + 1)^*(\varepsilon + 1)</tex>
 +
|<tex>\varnothing</tex>
 +
|-
 +
|<tex>R_{22}^{(1)}</tex>
 +
|<tex>\varepsilon + 0 + 1 + \varnothing(\varepsilon + 1)^*0</tex>
 +
|<tex>(\varepsilon + 0 + 1)</tex>
 +
|}
 +
<div style="clear:both;"></div>
 +
 
 +
И, наконец, последний шаг индукции
 +
 
 +
{| border="1" class="wikitable" style="width: 300px; height: 250px; float: left;"
 +
!style="background:#41aef0"|Выражение
 +
!style="background:#41aef0"|Упрощенное выражение (после подстановки)
 +
|-
 +
|<tex>R_{11}^{(1)}</tex>
 +
|<tex>1^*</tex>
 +
|-
 +
|<tex>R_{12}^{(1)}</tex>
 +
|<tex>1^*0(0 + 1)^*</tex>
 +
|-
 +
|<tex>R_{21}^{(1)}</tex>
 +
|<tex>\varnothing</tex>
 +
|-
 +
|<tex>R_{22}^{(1)}</tex>
 +
|<tex>(0 + 1)^*</tex>
 +
|}
 +
<div style="clear:both;"></div>
 +
 
 +
Окончательное регулярное выражение, эквивалентное автомату, строится путем объединения всех тех выражений, для которых первое состояние
 +
является начальным, а второе {{---}} заключительным.  В нашем примере <tex>1</tex> {{---}} начальное состояние, а <tex>2</tex> {{---}} заключительное, поэтому нам нужно лишь выражение <tex>R_{12}^{(1)}</tex>, равное <tex>1^*0(0 + 1)^*</tex>
 +
 
 +
Отметим, что первый вариант значительно короче. Для решения системы уравнений необходимо выполнить <tex>O(n)</tex> итераций, где <tex>n</tex> {{---}} число вершин. В каждом уравнении в худшем случае может быть <tex>|\Gamma| \cdot (n - 1)</tex> переменных в правой части {{---}} все возможные переходы по всем возможным состояниям. Теперь, для решения вторым вариантом, нам во-первых надо построить массив размера <tex>|\Gamma| \cdot n</tex> для всех переходов из всех состояний и выполнить столько же итераций, поскольку самый длинный путь в худшем случае будет проходить по всем переходам из всех вершин с возвращением в исходную, которая и будет являться терминальной, то есть в итоге сложность <tex>O((|\Gamma| \cdot n)^2)</tex>. Кроме того, в алгоритме на каждом шаге мы упрощали выражение, чтобы оно было более коротким. В общем случае длина выражения перед упрощением трудно поддается оценке, однако не стоит забывать про этот факт. В случае, если выражение не будет упрощаться, то по приведенной выше формуле итерации, оно, очевидно, с каждой итерацией будет значительно (степенная зависимость) расти.
  
 
== См. также ==
 
== См. также ==
 
* [[Теорема Клини (совпадение классов автоматных и регулярных языков) | Теорема Клини]]
 
* [[Теорема Клини (совпадение классов автоматных и регулярных языков) | Теорема Клини]]
 
* [[Решение уравнений в регулярных выражениях | Решение уравнений в регулярных выражениях ]]
 
* [[Решение уравнений в регулярных выражениях | Решение уравнений в регулярных выражениях ]]
 +
 +
== Источники информации==
 +
* [http://mathhelpplanet.com/static.php?p=teorema-klini Mathhelpplanet {{---}} Теорема Клини]
 +
* [https://drona.csa.iisc.ernet.in/~deepakd/atc-2011/regular-exp.pdf Deepak D’Souza {{---}} Regular Expressions]
 +
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. {{---}} М.: Издательский дом «Вильямс», 2008. {{---}} С. 112 {{---}} ISBN 978-5-8459-1347-0
 +
 +
 
[[Категория: Теория формальных языков]]
 
[[Категория: Теория формальных языков]]
 
[[Категория: Автоматы и регулярные языки]]
 
[[Категория: Автоматы и регулярные языки]]

Текущая версия на 21:20, 4 января 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]\varepsilon[/math] для терминального состояния, как это указано в доказательстве.

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

Отметим, что первый вариант значительно короче. Для решения системы уравнений необходимо выполнить [math]O(n)[/math] итераций, где [math]n[/math] — число вершин. В каждом уравнении в худшем случае может быть [math]|\Gamma| \cdot (n - 1)[/math] переменных в правой части — все возможные переходы по всем возможным состояниям. Теперь, для решения вторым вариантом, нам во-первых надо построить массив размера [math]|\Gamma| \cdot n[/math] для всех переходов из всех состояний и выполнить столько же итераций, поскольку самый длинный путь в худшем случае будет проходить по всем переходам из всех вершин с возвращением в исходную, которая и будет являться терминальной, то есть в итоге сложность [math]O((|\Gamma| \cdot n)^2)[/math]. Кроме того, в алгоритме на каждом шаге мы упрощали выражение, чтобы оно было более коротким. В общем случае длина выражения перед упрощением трудно поддается оценке, однако не стоит забывать про этот факт. В случае, если выражение не будет упрощаться, то по приведенной выше формуле итерации, оно, очевидно, с каждой итерацией будет значительно (степенная зависимость) расти.

См. также[править]

Источники информации[править]