Автоматы с eps-переходами. Eps-замыкание — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Эквивалентность автоматов с переходами по строкам и НКА. Eps-замыкание)
м (rollbackEdits.php mass rollback)
 
(не показано 20 промежуточных версий 7 участников)
Строка 1: Строка 1:
 
[[Категория: Теория формальных языков]]
 
[[Категория: Теория формальных языков]]
==Автоматы с eps-переходами==
+
==Автоматы с <tex  dpi = "155">\varepsilon</tex>-переходами==
Конечный автомат с <tex>\varepsilon</tex>-переходами --- конечный автомат, в котором есть возможность совершать переходы по <tex>\varepsilon</tex>.  
+
Конечный автомат с <tex>\varepsilon</tex>-переходами {{---}} конечный автомат, в котором есть возможность совершать переходы по <tex>\varepsilon</tex>.  
 
{{Определение
 
{{Определение
|definition=<tex>\varepsilon</tex>-НКА <tex>A</tex> --- это набор <tex>A={\langle\Sigma,Q,s,T,\delta\rangle}</tex>, где все компоненты имеют тот же смысл, что и для [[Недетерминированные конечные автоматы|НКА]], за исключением <tex>\delta : Q\times \Sigma\bigcup\{\varepsilon\} \to \cal P</tex><tex>(Q)</tex>.
+
|definition='''<tex>\varepsilon</tex>-НКА''' или '''НКА с <tex>\varepsilon</tex>-переходами''' (англ. ''<tex>\varepsilon</tex>-moves'') {{---}} набор <tex>A={\langle\Sigma,Q,s,T,\delta\rangle}</tex>, где все компоненты имеют тот же смысл, что и для [[Недетерминированные конечные автоматы|НКА]], за исключением <tex>\delta : Q\times (\Sigma\cup\{\varepsilon\}) \to 2^Q</tex>.
 
}}
 
}}
==Эквивалентность автоматов с переходами по строкам и НКА. Eps-замыкание==
+
 
Рассмотрим автомат, в котором переходы  осуществляются по строкам. Это переходы вида <tex>\langle p,\alpha\beta\rangle\vdash\langle q,\beta\rangle</tex>, где <tex>\alpha,\beta</tex> --- строки.
+
==Эквивалентность автоматов с переходами по строкам и НКА. <tex  dpi = "155">\varepsilon</tex>-замыкание==
 +
Будем называть два автомата '''эквивалентными''', если они задают один и тот же язык.<br>
 +
Рассмотрим автомат, в котором переходы  осуществляются по строкам. Это переходы вида <tex>\langle p,\alpha\beta\rangle\vdash\langle q,\beta\rangle</tex>, где <tex>\alpha,\beta</tex> {{---}} строки.
 
{{Теорема
 
{{Теорема
 
|id=th1
 
|id=th1
Строка 13: Строка 15:
 
|proof=
 
|proof=
 
Рассмотрим два случая:
 
Рассмотрим два случая:
* <tex>\left | \alpha \right | \ge 1</tex>
+
* <tex>\left | \alpha \right | \geqslant 1</tex>
*:Заменим переходы по таким строкам на последовательности переходов по символам. А именно, пусть <tex>\alpha=a_1a_2...a_n</tex>, где <tex>a_1,a_2,...,a_n</tex> --- символы. Заменим переход <tex>\langle p,\alpha\beta\rangle\vdash\langle q,\beta\rangle</tex> на переходы <tex>{\langle p,\alpha\beta\rangle\vdash\langle t_1, a_1^{-1}\alpha\beta\rangle},{\langle t_1,a_1^{-1}\alpha\beta\rangle\vdash\langle t_2,(a_1a_2)^{-1}\alpha\beta\rangle},...,{\langle t_{n-1}, a_n\rangle\vdash\langle q, \beta\rangle}.</tex>
+
*:Заменим переходы по таким строкам на последовательности переходов по символам. А именно, пусть <tex>\alpha=a_1a_2 \ldots a_n</tex>, где <tex>a_1,a_2, \ldots ,a_n</tex> {{---}} символы. Заменим переход <tex>\langle p,\alpha\beta\rangle\vdash\langle q,\beta\rangle</tex> на переходы <tex>{\langle p,\alpha\beta\rangle\vdash\langle t_1, a_1^{-1}\alpha\beta\rangle},{\langle t_1,a_1^{-1}\alpha\beta\rangle\vdash\langle t_2,(a_1a_2)^{-1}\alpha\beta\rangle}, \ldots ,{\langle t_{n-1}, a_n\beta\rangle\vdash\langle q, \beta\rangle}.</tex>
 
* <tex>\left | \alpha \right | = 0 \Rightarrow \alpha = \varepsilon</tex>
 
* <tex>\left | \alpha \right | = 0 \Rightarrow \alpha = \varepsilon</tex>
*:Рассматриваем '''автомат <tex>A</tex> с <tex>\varepsilon</tex>-переходами.''' Для доказательства его эквивалентности НКА посторим его <tex>\varepsilon</tex>-замыкание.
+
*:Рассматриваем '''автомат <tex>A</tex> с <tex>\varepsilon</tex>-переходами.''' Для доказательства его эквивалентности НКА построим его <tex>\varepsilon</tex>-замыкание.
 
*:{{Определение
 
*:{{Определение
 
|definition=
 
|definition=
<tex>\varepsilon</tex>-замыкание (<tex>\varepsilon</tex>-closure) --- построение по автомату с <tex>\varepsilon</tex>-переходами эквивалентного ему автомата без <tex>\varepsilon</tex>-переходов.
+
'''<tex>\varepsilon</tex>-замыкание''' (англ. ''<tex>\varepsilon</tex>-closure'') {{---}} построение по автомату с <tex>\varepsilon</tex>-переходами эквивалентного ему автомата без <tex>\varepsilon</tex>-переходов.
 
}}
 
}}
 
Ход построения <tex>\varepsilon</tex>-замыкания:
 
Ход построения <tex>\varepsilon</tex>-замыкания:
 
#Транзитивное замыкание
 
#Транзитивное замыкание
#:Пусть <tex>B</tex> - подграф <tex>A</tex>, в котором есть только <tex>\varepsilon</tex>-переходы. Сделаем транзитивное замыкание графа <tex>B</tex>. Таким образом, получим из автомата <tex>A</tex> новый автомат <tex>A_1</tex>, который допускает тот же язык. Заметим, что если <tex>A_1</tex> допускает слово <tex>x</tex>, то он допускает <tex>x</tex>, не совершая двух <tex>\varepsilon</tex>-переходов подряд.
+
#:Пусть <tex>B</tex> {{---}} подграф <tex>A</tex>, в котором есть только <tex>\varepsilon</tex>-переходы. Сделаем транзитивное замыкание графа <tex>B</tex>. Таким образом, получим из автомата <tex>A</tex> новый автомат <tex>A_1</tex>, который допускает тот же язык. Заметим, что если <tex>A_1</tex> допускает слово <tex>x</tex>, то он допускает <tex>x</tex>, не совершая двух <tex>\varepsilon</tex>-переходов подряд.
 
#Добавление допускающих состояний
 
#Добавление допускающих состояний
#:Пусть в <tex>A_1</tex> есть <tex>\varepsilon</tex>-переход из состояния <tex>u</tex> в состояние <tex>v</tex>, причем <tex>v</tex> - допускающее. Тогда, если текущее состояние <tex>u</tex> и строка закончилась, то ее можно допустить. Во всех таких случаях сделаем <tex>u</tex> допускающим. Получим автомат <tex>A_2</tex>, обладающий тем же свойством, что и <tex>A_1</tex>, а также не совершающий <tex>\varepsilon</tex>-переходов в качестве последнего перехода.
+
#:Пусть в <tex>A_1</tex> есть <tex>\varepsilon</tex>-переход из состояния <tex>u</tex> в состояние <tex>v</tex>, причем <tex>v</tex> {{---}} допускающее. Тогда, если текущее состояние <tex>u</tex> и строка закончилась, то её можно допустить. Во всех таких случаях сделаем <tex>u</tex> допускающим. Получим автомат <tex>A_2</tex>, обладающий тем же свойством, что и <tex>A_1</tex>, а также не совершающий <tex>\varepsilon</tex>-переходов в качестве последнего перехода.
#Добавление ребер
+
#Добавление рёбер
#:Во всех случаях, когда <tex>{\delta(u,\varepsilon)=v}, {\delta(v,c)=w}</tex>, добавим переход <tex>\delta(u,c)=w</tex>. Заметим, что если полученный автомат <tex>A_3</tex> допускает <tex>x</tex>, то он допускает <tex>x</tex> не совершая <tex>\varepsilon</tex>-переходов.
+
#:Во всех случаях, когда <tex>{\delta(u,\varepsilon)=v}, {\delta(v,c)=w}</tex>, добавим переход <tex>\delta(u,c)=w</tex>. Заметим, что если полученный автомат <tex>A_3</tex> допускает <tex>x</tex>, то он допускает <tex>x</tex>, не совершая <tex>\varepsilon</tex>-переходов.
 
#Устранение <tex>\varepsilon</tex>-переходов
 
#Устранение <tex>\varepsilon</tex>-переходов
 
#:Из предыдущего замечания следует, что если теперь устранить <tex>\varepsilon</tex>-переходы, то допускаемый язык не изменится. Уберем из <tex>A_3</tex> все <tex>\varepsilon</tex>-переходы.
 
#:Из предыдущего замечания следует, что если теперь устранить <tex>\varepsilon</tex>-переходы, то допускаемый язык не изменится. Уберем из <tex>A_3</tex> все <tex>\varepsilon</tex>-переходы.
Получили НКА без <tex>\varepsilon</tex>-переходов эквивалентный исходному автомату.
+
Получили НКА без <tex>\varepsilon</tex>-переходов, эквивалентный исходному автомату.
 
}}
 
}}
  
==Совпадение множеств языков, допускаемых eps-НКА и ДКА==
+
==Совпадение множеств языков, допускаемых <tex  dpi = "155">\varepsilon</tex>-НКА и ДКА==
 
{{Утверждение
 
{{Утверждение
 
|id=th2
 
|id=th2
 
|statement=
 
|statement=
 
Множество языков, допускаемых автоматами с <tex>\varepsilon</tex>-переходами, совпадает с множеством языков, допускаемых [[Детерминированные_конечные_автоматы|детерминированными конечными автоматами]].
 
Множество языков, допускаемых автоматами с <tex>\varepsilon</tex>-переходами, совпадает с множеством языков, допускаемых [[Детерминированные_конечные_автоматы|детерминированными конечными автоматами]].
|proof=[[Построение_по_НКА_эквивалентного_ДКА,_алгоритм_Томпсона|L(ДКА) = L(НКА)]]. По только что доказанной теореме, L(НКА) = L(<tex>\varepsilon</tex>-НКА). Значит, L(ДКА) = L(<tex>\varepsilon</tex>-НКА).
+
|proof=[[Построение_по_НКА_эквивалентного_ДКА,_алгоритм_Томпсона|<tex> \mathcal{L}(</tex>ДКА<tex>) = \mathcal{L}(</tex>НКА<tex>)</tex>]]. По только что доказанной теореме, <tex> \mathcal{L}(</tex>НКА<tex>) = \mathcal{L}(</tex><tex>\varepsilon</tex>-НКА<tex>)</tex>. Значит, <tex> \mathcal{L}(</tex>ДКА<tex>) = \mathcal{L}(</tex><tex>\varepsilon</tex>-НКА<tex>)</tex>.
 
}}
 
}}
 +
 +
== Применение ==
 +
В некоторых случаях НКА с <tex>\varepsilon</tex>-переходами строятся проще, чем просто НКА и тем более ДКА для тех же языков. Доказанная выше эквивалентность <tex> \mathcal{L}(</tex>ДКА<tex>)</tex>,<tex>\mathcal{L}(</tex>НКА<tex>)</tex> и <tex>\mathcal{L}(</tex><tex>\varepsilon</tex>-НКА<tex>)</tex> позволяет нам при помощи алгоритма <tex>\varepsilon</tex>-замыкания легко приводить одно к другому и далее к третьему. Также свойства, доказанные выше, являются важной составляющей доказательства [[Теорема Клини (совпадение классов автоматных и регулярных языков)| теоремы Клини]].
 +
 +
==См. также==
 +
*[[Недетерминированные конечные автоматы]]
 +
*[[Теорема Клини (совпадение классов автоматных и регулярных языков)]]
 +
 +
==Источники информации==
 +
*[http://en.wikipedia.org/wiki/Nondeterministic_finite_automaton Wikipedia — Nondeterministic finite automaton]
 +
*[http://en.wikipedia.org/wiki/Nondeterministic_finite_automaton_with_%CE%B5-moves Wikipedia — Nondeterministic finite automaton with epsilon-moves]
 +
 +
[[Категория: Теория формальных языков]]
 +
[[Категория: Автоматы и регулярные языки]]

Текущая версия на 19:05, 4 сентября 2022

Автоматы с [math]\varepsilon[/math]-переходами

Конечный автомат с [math]\varepsilon[/math]-переходами — конечный автомат, в котором есть возможность совершать переходы по [math]\varepsilon[/math].

Определение:
[math]\varepsilon[/math]-НКА или НКА с [math]\varepsilon[/math]-переходами (англ. [math]\varepsilon[/math]-moves) — набор [math]A={\langle\Sigma,Q,s,T,\delta\rangle}[/math], где все компоненты имеют тот же смысл, что и для НКА, за исключением [math]\delta : Q\times (\Sigma\cup\{\varepsilon\}) \to 2^Q[/math].


Эквивалентность автоматов с переходами по строкам и НКА. [math]\varepsilon[/math]-замыкание

Будем называть два автомата эквивалентными, если они задают один и тот же язык.
Рассмотрим автомат, в котором переходы осуществляются по строкам. Это переходы вида [math]\langle p,\alpha\beta\rangle\vdash\langle q,\beta\rangle[/math], где [math]\alpha,\beta[/math] — строки.

Теорема:
Автоматы с переходами по строкам эквивалентны недетерминированным конечным автоматам.
Доказательство:
[math]\triangleright[/math]

Рассмотрим два случая:

  • [math]\left | \alpha \right | \geqslant 1[/math]
    Заменим переходы по таким строкам на последовательности переходов по символам. А именно, пусть [math]\alpha=a_1a_2 \ldots a_n[/math], где [math]a_1,a_2, \ldots ,a_n[/math] — символы. Заменим переход [math]\langle p,\alpha\beta\rangle\vdash\langle q,\beta\rangle[/math] на переходы [math]{\langle p,\alpha\beta\rangle\vdash\langle t_1, a_1^{-1}\alpha\beta\rangle},{\langle t_1,a_1^{-1}\alpha\beta\rangle\vdash\langle t_2,(a_1a_2)^{-1}\alpha\beta\rangle}, \ldots ,{\langle t_{n-1}, a_n\beta\rangle\vdash\langle q, \beta\rangle}.[/math]
  • [math]\left | \alpha \right | = 0 \Rightarrow \alpha = \varepsilon[/math]
    Рассматриваем автомат [math]A[/math] с [math]\varepsilon[/math]-переходами. Для доказательства его эквивалентности НКА построим его [math]\varepsilon[/math]-замыкание.
Определение:
[math]\varepsilon[/math]-замыкание (англ. [math]\varepsilon[/math]-closure) — построение по автомату с [math]\varepsilon[/math]-переходами эквивалентного ему автомата без [math]\varepsilon[/math]-переходов.

Ход построения [math]\varepsilon[/math]-замыкания:

  1. Транзитивное замыкание
    Пусть [math]B[/math] — подграф [math]A[/math], в котором есть только [math]\varepsilon[/math]-переходы. Сделаем транзитивное замыкание графа [math]B[/math]. Таким образом, получим из автомата [math]A[/math] новый автомат [math]A_1[/math], который допускает тот же язык. Заметим, что если [math]A_1[/math] допускает слово [math]x[/math], то он допускает [math]x[/math], не совершая двух [math]\varepsilon[/math]-переходов подряд.
  2. Добавление допускающих состояний
    Пусть в [math]A_1[/math] есть [math]\varepsilon[/math]-переход из состояния [math]u[/math] в состояние [math]v[/math], причем [math]v[/math] — допускающее. Тогда, если текущее состояние [math]u[/math] и строка закончилась, то её можно допустить. Во всех таких случаях сделаем [math]u[/math] допускающим. Получим автомат [math]A_2[/math], обладающий тем же свойством, что и [math]A_1[/math], а также не совершающий [math]\varepsilon[/math]-переходов в качестве последнего перехода.
  3. Добавление рёбер
    Во всех случаях, когда [math]{\delta(u,\varepsilon)=v}, {\delta(v,c)=w}[/math], добавим переход [math]\delta(u,c)=w[/math]. Заметим, что если полученный автомат [math]A_3[/math] допускает [math]x[/math], то он допускает [math]x[/math], не совершая [math]\varepsilon[/math]-переходов.
  4. Устранение [math]\varepsilon[/math]-переходов
    Из предыдущего замечания следует, что если теперь устранить [math]\varepsilon[/math]-переходы, то допускаемый язык не изменится. Уберем из [math]A_3[/math] все [math]\varepsilon[/math]-переходы.
Получили НКА без [math]\varepsilon[/math]-переходов, эквивалентный исходному автомату.
[math]\triangleleft[/math]

Совпадение множеств языков, допускаемых [math]\varepsilon[/math]-НКА и ДКА

Утверждение:
Множество языков, допускаемых автоматами с [math]\varepsilon[/math]-переходами, совпадает с множеством языков, допускаемых детерминированными конечными автоматами.
[math]\triangleright[/math]
[math] \mathcal{L}([/math]ДКА[math]) = \mathcal{L}([/math]НКА[math])[/math]. По только что доказанной теореме, [math] \mathcal{L}([/math]НКА[math]) = \mathcal{L}([/math][math]\varepsilon[/math]-НКА[math])[/math]. Значит, [math] \mathcal{L}([/math]ДКА[math]) = \mathcal{L}([/math][math]\varepsilon[/math]-НКА[math])[/math].
[math]\triangleleft[/math]

Применение

В некоторых случаях НКА с [math]\varepsilon[/math]-переходами строятся проще, чем просто НКА и тем более ДКА для тех же языков. Доказанная выше эквивалентность [math] \mathcal{L}([/math]ДКА[math])[/math],[math]\mathcal{L}([/math]НКА[math])[/math] и [math]\mathcal{L}([/math][math]\varepsilon[/math]-НКА[math])[/math] позволяет нам при помощи алгоритма [math]\varepsilon[/math]-замыкания легко приводить одно к другому и далее к третьему. Также свойства, доказанные выше, являются важной составляющей доказательства теоремы Клини.

См. также

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