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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «== Альтернативное доказательство == == Пример == Категория: Теория формальных языков [[Ка...»)
 
Строка 1: Строка 1:
 
== Альтернативное доказательство ==
 
== Альтернативное доказательство ==
 +
 +
{{Теорема
 +
|statement=Класс [[Детерминированные_конечные_автоматы#Автоматные_языки | автоматных]] языков является подмножеством [[Регулярные языки:_два определения_и_их_эквивалентность#REG1 | регулярных]].
 +
|proof=
 +
 +
Рассмотрим автоматный язык <tex>L</tex> и ДКА для него. Для доказательства теоремы достаточно построить регулярное выражение, порождающее язык <tex>L</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>с</tex>, то слово <tex>с \alpha</tex> принаджелит языку <tex>L_i</tex>. Также, если <tex>\epsilon \in \L_0</tex>, то есть если стартовое состояние является и терминальным тоже, то добавим в сумму для <tex>L_0</tex> и <tex>\epsilon</tex>.
 +
 +
Заметим, что <tex>L_0 = L</tex>.
 +
}}
 
== Пример ==
 
== Пример ==
  
 
[[Категория: Теория формальных языков]]
 
[[Категория: Теория формальных языков]]
 
[[Категория: Автоматы и регулярные языки]]
 
[[Категория: Автоматы и регулярные языки]]

Версия 19:01, 24 октября 2013

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

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

Рассмотрим автоматный язык [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]с[/math], то слово [math]с \alpha[/math] принаджелит языку [math]L_i[/math]. Также, если [math]\epsilon \in \L_0[/math], то есть если стартовое состояние является и терминальным тоже, то добавим в сумму для [math]L_0[/math] и [math]\epsilon[/math].

Заметим, что [math]L_0 = L[/math].
[math]\triangleleft[/math]

Пример