10
правок
Изменения
Новая страница: «{{Теорема |author=Клини |statement=Классы автоматных и регулярных языков совпадают. <tex>Reg = Aut</tex> |proof…»
{{Теорема
|author=Клини
|statement=Классы автоматных и регулярных языков совпадают. <tex>Reg = Aut</tex>
|proof=
[[Файл:Reg0.png|200px|thumb|right|Автоматы для регулярных языков нулевого поколения]]
[[Файл:cup.png|200px|thumb|right|Автомат для объединения двух регулярных языков]]
[[Файл:concat.png|200px|thumb|right|Автомат для конкатенации двух регулярных языков]]
[[Файл:Klenee.png|200px|thumb|right|Автомат для замыкания Клини регулярного языка]]
1. <tex>Reg \subset Aut</tex>
Для доказательства будем строить автоматы, допускающие регулярные языки. При этом будем использовать индукцию по номеру поколения регулярного языка.
*'''База.''' <tex>n = 0</tex>
Для этого достаточно построить автоматы для трех языков:
**<tex>L = \varnothing</tex>
**<tex>L = \left\{\varepsilon \right\}</tex>
**<tex>L = \left\{c \right\}</tex>
*'''Индукционный переход'''. Умеем строить автоматы для языков<tex>n</tex>-ого поколения. Будем строить для <tex>n + 1</tex>.
Для этого достаточно научиться строить автоматы для следующих языков (<tex>L1, L2 \in Reg_n</tex>):
**<tex>L = L \cup M</tex>
**<tex>L = LM</tex>
**<tex>L = L^*</tex>
Заметим, что по предположению индукции автоматы для <tex>L, M</tex> могут быть построены.
Итого, мы можем по регулярному выражению построить автомат, допускающий тот же язык.
2. <tex>Aut \subset Reg</tex>
Для доказательства будем строить регулярное выражение, допускающее язык, заданный каким-то автоматом. Пусть задан автомат <tex>A</tex> с набором состояний <tex>Q = \left\{1, 2, \dots n \right\}</tex>.
Определим регулярные выражения, задающие следующие множества слов:
<tex>\xi_{ijk} = \left\{ s \mid <i,s> \vdash^* <j, \varepsilon> \right\} </tex>, причем в качестве промежуточных вершин выступают только такие, у которых номер не более <tex>k</tex>.
Построим эти регулярные выражения:
*<tex>\xi_{ii0} = \varepsilon \mid c_1 \mid \dots \mid c_l</tex> , где <tex>c_1, c_2, \dots c_l</tex> символы, по которым есть переход из состояния ''i'' в него же самого.
*<tex>\xi_{ij0} = c_1 \mid \dots \mid c_l</tex>, где <tex>c_1, c_2, \dots c_l</tex> символы, по которым есть переход из состояния ''i'' в состояние ''j''.
*<tex>\xi_{ijk} = \xi_{ij{k-1}} \mid \xi_{ik{k-1}} (\xi_{kk{k-1}})^* \xi_{kj{k-1}}</tex>
Теперь нетрудно задать регулярное выражение для всего языка:
<tex>\varphi = \xi_{s{t_1}n} \mid \xi_{s{t_1}n} \mid \dots \mid \xi_{s{t_r}n}</tex>, где <tex>s</tex> - стартовое состояние, а <tex>t_1, t_2, \dots t_r</tex> - терминальные состояния исходного автомата.
Таким образом мы построили по автомату регулярное выражение, допускающее тот же самый язык.
}}
|author=Клини
|statement=Классы автоматных и регулярных языков совпадают. <tex>Reg = Aut</tex>
|proof=
[[Файл:Reg0.png|200px|thumb|right|Автоматы для регулярных языков нулевого поколения]]
[[Файл:cup.png|200px|thumb|right|Автомат для объединения двух регулярных языков]]
[[Файл:concat.png|200px|thumb|right|Автомат для конкатенации двух регулярных языков]]
[[Файл:Klenee.png|200px|thumb|right|Автомат для замыкания Клини регулярного языка]]
1. <tex>Reg \subset Aut</tex>
Для доказательства будем строить автоматы, допускающие регулярные языки. При этом будем использовать индукцию по номеру поколения регулярного языка.
*'''База.''' <tex>n = 0</tex>
Для этого достаточно построить автоматы для трех языков:
**<tex>L = \varnothing</tex>
**<tex>L = \left\{\varepsilon \right\}</tex>
**<tex>L = \left\{c \right\}</tex>
*'''Индукционный переход'''. Умеем строить автоматы для языков<tex>n</tex>-ого поколения. Будем строить для <tex>n + 1</tex>.
Для этого достаточно научиться строить автоматы для следующих языков (<tex>L1, L2 \in Reg_n</tex>):
**<tex>L = L \cup M</tex>
**<tex>L = LM</tex>
**<tex>L = L^*</tex>
Заметим, что по предположению индукции автоматы для <tex>L, M</tex> могут быть построены.
Итого, мы можем по регулярному выражению построить автомат, допускающий тот же язык.
2. <tex>Aut \subset Reg</tex>
Для доказательства будем строить регулярное выражение, допускающее язык, заданный каким-то автоматом. Пусть задан автомат <tex>A</tex> с набором состояний <tex>Q = \left\{1, 2, \dots n \right\}</tex>.
Определим регулярные выражения, задающие следующие множества слов:
<tex>\xi_{ijk} = \left\{ s \mid <i,s> \vdash^* <j, \varepsilon> \right\} </tex>, причем в качестве промежуточных вершин выступают только такие, у которых номер не более <tex>k</tex>.
Построим эти регулярные выражения:
*<tex>\xi_{ii0} = \varepsilon \mid c_1 \mid \dots \mid c_l</tex> , где <tex>c_1, c_2, \dots c_l</tex> символы, по которым есть переход из состояния ''i'' в него же самого.
*<tex>\xi_{ij0} = c_1 \mid \dots \mid c_l</tex>, где <tex>c_1, c_2, \dots c_l</tex> символы, по которым есть переход из состояния ''i'' в состояние ''j''.
*<tex>\xi_{ijk} = \xi_{ij{k-1}} \mid \xi_{ik{k-1}} (\xi_{kk{k-1}})^* \xi_{kj{k-1}}</tex>
Теперь нетрудно задать регулярное выражение для всего языка:
<tex>\varphi = \xi_{s{t_1}n} \mid \xi_{s{t_1}n} \mid \dots \mid \xi_{s{t_r}n}</tex>, где <tex>s</tex> - стартовое состояние, а <tex>t_1, t_2, \dots t_r</tex> - терминальные состояния исходного автомата.
Таким образом мы построили по автомату регулярное выражение, допускающее тот же самый язык.
}}
