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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Альтернативное доказательство)
м (Альтернативное доказательство)
Строка 10: Строка 10:
 
Пусть наш автомат состоит из <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>\epsilon \in L_0</tex>, то есть, если стартовое состояние является и терминальным тоже, то добавим в сумму для <tex>L_0</tex> и <tex>\epsilon</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_0</tex>, то есть, если стартовое состояние является и терминальным тоже, то добавим в сумму для <tex>L_0</tex> и <tex>\varepsilon</tex>.
  
Мы получили [[Решение уравнений в регулярных выражениях#Решение системы уравнений в регулярных выражениях | систему]] из <tex>n</tex> регулярных выражений с <tex>n</tex> неизвестными, причем <tex> \epsilon \notin \alpha_{ij}</tex> для всех <tex> i </tex> и <tex> j </tex>, так как в автомате нет <tex> \epsilon </tex>-переходов, а, следовательно, система имеет единственное решение. Также заметим, что <tex>L_0</tex> содержит слова, по которым из стартового состояния можно дойти до терминального, но тогда <tex>L_0 = L</tex>.
+
Мы получили [[Решение уравнений в регулярных выражениях#Решение системы уравнений в регулярных выражениях | систему]] из <tex>n</tex> регулярных выражений с <tex>n</tex> неизвестными, причем <tex> \varepsilon \notin \alpha_{ij}</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>.

Версия 16:16, 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+\epsilon \\ 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] \epsilon \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 + \epsilon [/math].

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