Изменения
Нет описания правки
{{Теорема
|author=Клини
|statement=Классы автоматных и регулярных языков совпадают. , то есть <tex>Reg = Aut</tex>.
|proof=
[[Файл:Reg0.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>L, M \in Reg_n</tex>):
*<tex>L^\prime = L \cup M</tex>;,*<tex>L^\prime = LM</tex>;,
*<tex>L^\prime = L^*</tex>.
Заметим, что по предположению индукции автоматы для <tex>L, M</tex> могут быть построены.
Итого, мы можем по регулярному выражению построить автомат, допускающий тот же язык.
2. <tex>Aut \subset Reg</tex>.
Для доказательства будем строить регулярное выражение, допускающее язык, заданный каким-то автоматом. Пусть задан автомат <tex>A</tex> с набором состояний <tex>Q = \left\{1, 2, \dots n \right\}</tex>.
