Изменения

1. *<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</tex>-ого поколения. Будем строить для <tex>n + 1</tex>.:Для этого достаточно научиться строить автоматы для следующих языков (<tex>L, M \in \mathrm{R_n}</tex>): *:#<tex>L^\prime = L \cup M</tex>,*:#<tex>L^\prime = LM</tex>,*:#<tex>L^\prime = L^*</tex>.

'''Итого''', мы можем по регулярному выражению построить автомат, допускающий тот же язык.

2. <br>*<tex>\mathrm{AUT} \subseteq \mathrm{REG}</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} = (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_2}n} \mid \dots \mid \xi_{s{t_r}n}</tex>, где <tex>s</tex> — стартовое состояние, а <tex>t_1, t_2, \dots t_r</tex> — терминальные состояния исходного автомата.

'''Таким образом''', мы построили по автомату регулярное выражение, допускающее тот же самый язык.