170
правок
Изменения
Нет описания правки
{{Теорема
|author=Клини
|statement=Классы [[Детерминированные_конечные_автоматы#Автоматные_языки | автоматных ]] и [[Регулярные языки:_два определения_и_их_эквивалентность | регулярных ]] языков совпадают.
|proof=
[[Файл:Reg0.png|200px|thumb|right|Автоматы для регулярных языков нулевого поколения]]
[[Файл:concat.png|200px|thumb|right|Автомат для конкатенации двух регулярных языков]]
[[Файл:Klenee.png|200px|thumb|right|Автомат для замыкания Клини регулярного языка]]
1. <tex>Reg \mathrm{REG} \subseteq Aut\mathrm{AUT}</tex>.
Для доказательства будем строить автоматы, допускающие регулярные языки (см. картинки справа). При этом будем использовать индукцию по номеру поколения регулярного языка.
'''Индукционный переход'''. Умеем строить автоматы для языков <tex>n</tex>-ого поколения. Будем строить для <tex>n + 1</tex>.
Для этого достаточно научиться строить автоматы для следующих языков (<tex>L, M \in Reg_n\mathrm{R_n}</tex>):
*<tex>L^\prime = L \cup M</tex>,
*<tex>L^\prime = LM</tex>,
Итого, мы можем по регулярному выражению построить автомат, допускающий тот же язык.
2. <tex>Aut \mathrm{AUT} \subseteq Reg\mathrm{REG}</tex>.
Для доказательства будем строить регулярное выражение, допускающее язык, заданный каким-то автоматом. Пусть задан автомат <tex>A</tex> с набором состояний <tex>Q = \left\{1, 2, \dots n \right\}</tex>.
