142
правки
Изменения
Нет описания правки
[[Файл:concat.png|200px|thumb|right|Автомат для конкатенации двух регулярных языков]]
[[Файл:Klenee.png|200px|thumb|right|Автомат для замыкания Клини регулярного языка]]
1. <tex>Reg \subset subseteq Aut</tex>.
Для доказательства будем строить автоматы, допускающие регулярные языки (см. картинки справа). При этом будем использовать индукцию по номеру поколения регулярного языка.
Итого, мы можем по регулярному выражению построить автомат, допускающий тот же язык.
2. <tex>Aut \subset subseteq Reg</tex>.
Для доказательства будем строить регулярное выражение, допускающее язык, заданный каким-то автоматом. Пусть задан автомат <tex>A</tex> с набором состояний <tex>Q = \left\{1, 2, \dots n \right\}</tex>.
