211
правок
Изменения
м
Нет описания правки
'''База.''' <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> могут быть построены.
Построим эти регулярные выражения:
*<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_{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_2}n} \mid \dots \mid \xi_{s{t_r}n}</tex>, где <tex>s</tex> - — стартовое состояние, а <tex>t_1, t_2, \dots t_r</tex> - — терминальные состояния исходного автомата.
Таким образом , мы построили по автомату регулярное выражение, допускающее тот же самый язык.
}}
