Изменения

Перейти к: навигация, поиск
Источники информации
{{Теорема
|author=Клини
|statement=Классы [[Детерминированные_конечные_автоматы#Автоматные_языки | автоматных ]] и [[Регулярные языки:_два определения_и_их_эквивалентность#REG1 | регулярных ]] языков совпадают. <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>\mathrm{REG} \subseteq \mathrm{AUT}</tex>.
'''База.''' <tex>n = 0</tex>Для этого достаточно построить доказательства будем строить автоматы для трех языков:*<tex>L = \varnothing</tex>*<tex>L = \left\{\varepsilon \right\}</tex>*<tex>L = \left\{c \right\}</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\mathrm{R_n}</tex>): *:#<tex>L^\prime = L \cup M</tex>,*:#<tex>L^\prime = LM</tex>,*:#<tex>L^\prime = L^*</tex>.
Заметим, что по предположению индукции автоматы для <tex>L, M</tex> могут быть построены.
'''Итого''', мы можем по регулярному выражению построить автомат, допускающий тот же язык.
2. <br>*<tex>Aut \subset Regmathrm{AUT} \subseteq \mathrm{REG}</tex>.
Для доказательства будем строить регулярное выражение, допускающее язык, заданный каким-то автоматом. Пусть задан автомат <tex>A</tex> с набором состояний <tex>Q = \left\{1, 2, \dots n \right\}</tex>.
Определим регулярные выражения, задающие следующие множества слов:
:<tex>\xi_{ijk} = \left\{ s \mid \langle i,s \rangle \vdash^* \langle j, \varepsilon \rangle \right\} </tex>, причем в качестве промежуточных вершин выступают только такие, у которых номер не более <tex>k</tex>.<br>
Построим эти регулярные выражения:
*#<tex>\xi_{ii0} = \varepsilon \mid (c_1 \mid \dots \mid c_l)^*</tex> , где <tex>c_1, c_2, \dots c_l</tex> символы, по которым есть переход из состояния ''<tex>i'' </tex> в него же самого.*#<tex>\xi_{ij0} = c_1 \mid \dots \mid c_l</tex>, где <tex>c_1, c_2, \dots c_l</tex> символы, по которым есть переход из состояния ''<tex>i'' </tex> в состояние ''<tex>j''</tex>.#<tex>\xi_{iik} = (\xi_{ii{k-1}} \mid \xi_{ik{k-1}} (\xi_{kk{k-1}})^* \xi_{ki{k-1}} )^*</tex>. #<tex>\xi_{ijk} = \xi_{ij{k-1}} \mid \xi_{ik{k-1}} (\xi_{kk{k-1}})^* \xi_{kj{k-1}}</tex> .<br>
Теперь нетрудно задать регулярное выражение для всего языка:
:<tex>\varphi = \xi_{s{t_1}n} \mid \xi_{s{t_1t_2}n} \mid \dots \mid \xi_{s{t_r}n}</tex>, где <tex>s</tex> - стартовое состояние, а <tex>t_1, t_2, \dots t_r</tex> - терминальные состояния исходного автомата.
'''Таким образом ''', мы построили по автомату регулярное выражение, допускающее тот же самый язык.
}}
 
== См. также ==
* [[Регулярные языки: два определения и их эквивалентность]]
* [[Детерминированные конечные автоматы]]
 
== Источники информации==
* [https://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%9A%D0%BB%D0%B8%D0%BD%D0%B8 Википедия {{---}} Теорема Клини]
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. — М.:Издательский дом «Вильямс», 2002. — С. 61.— ISBN 5-8459-0261-4
 
 
[[Категория: Теория формальных языков]]
[[Категория: Автоматы и регулярные языки]]
Анонимный участник

Навигация