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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
м (Пример)
Строка 23: Строка 23:
 
<tex>
 
<tex>
 
\begin{cases}
 
\begin{cases}
L_0 = 0L_0+1L_1+\epsilon \\
+
L_0 = 0L_0+1L_1+\varepsilon \\
 
L_1 = 1L_0+0L_2 \\
 
L_1 = 1L_0+0L_2 \\
 
L_2 = 0L_1+1L_2
 
L_2 = 0L_1+1L_2
Строка 33: Строка 33:
 
<tex>L_2 = (00 + 1)L_2+01L_1</tex>.
 
<tex>L_2 = (00 + 1)L_2+01L_1</tex>.
  
Так как <tex> \epsilon \notin (00 + 1) </tex>, то <tex>L_2 = (00+1)^*01L_0</tex>.
+
Так как <tex> \varepsilon \notin (00 + 1) </tex>, то <tex>L_2 = (00+1)^*01L_0</tex>.
  
 
Подставим <tex>L_2</tex> во второе уравнение, а потом получившееся выражение подставим в первое, чтобы найти <tex>L_0</tex>:
 
Подставим <tex>L_2</tex> во второе уравнение, а потом получившееся выражение подставим в первое, чтобы найти <tex>L_0</tex>:
  
<tex>L_0 = 0L_0 + 11L_0 + 10(00+1)^*01L_0 + \epsilon </tex>.
+
<tex>L_0 = 0L_0 + 11L_0 + 10(00+1)^*01L_0 + \varepsilon </tex>.
  
Решив уравнение, получим что <tex>(0 + 11 + 10(00+1)^*01)^*</tex> {{---}} регулярное выражение, порождающее искомый язык. Отметим, что длина итогового регулярного выражения заметно короче, чем если бы мы строили его классическим способом.  
+
Решив уравнение, получим что <tex>(0 + 11 + 10(00+1)^*01)^*</tex> {{---}} регулярное выражение, порождающее искомый язык. Отметим, что длина итогового регулярного выражения заметно короче, чем если бы мы строили его классическим способом.
  
 
== См. также ==
 
== См. также ==

Версия 16:25, 26 октября 2013

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

Теорема:
Класс автоматных языков является подмножеством регулярных.
Доказательство:
[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 = \sum 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_0[/math], то есть, если стартовое состояние является и терминальным тоже, то добавим в сумму для [math]L_0[/math] и [math]\varepsilon[/math].

Мы получили систему из [math]n[/math] регулярных выражений с [math]n[/math] неизвестными, причем [math] \varepsilon \notin \alpha_{ij}[/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]

Пример

Автомат2.png

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

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

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

[math]L_2 = (00 + 1)L_2+01L_1[/math].

Так как [math] \varepsilon \notin (00 + 1) [/math], то [math]L_2 = (00+1)^*01L_0[/math].

Подставим [math]L_2[/math] во второе уравнение, а потом получившееся выражение подставим в первое, чтобы найти [math]L_0[/math]:

[math]L_0 = 0L_0 + 11L_0 + 10(00+1)^*01L_0 + \varepsilon [/math].

Решив уравнение, получим что [math](0 + 11 + 10(00+1)^*01)^*[/math] — регулярное выражение, порождающее искомый язык. Отметим, что длина итогового регулярного выражения заметно короче, чем если бы мы строили его классическим способом.

См. также