10
правок
Изменения
м
*'''База.''' <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 = L \cup M</tex>**<tex>L = LM</tex>**<tex>L = L^*</tex>
Исправил списки, сделал хорошие угловые скобки вместо уродских
Для доказательства будем строить автоматы, допускающие регулярные языки. При этом будем использовать индукцию по номеру поколения регулярного языка.
Для этого достаточно построить автоматы для трех языков:
Для этого достаточно научиться строить автоматы для следующих языков (<tex>L1, L2 \in Reg_n</tex>):
Заметим, что по предположению индукции автоматы для <tex>L, M</tex> могут быть построены.
Определим регулярные выражения, задающие следующие множества слов:
<tex>\xi_{ijk} = \left\{ s \mid <\langle i,s> \rangle \vdash^* <\langle j, \varepsilon> \rangle \right\} </tex>, причем в качестве промежуточных вершин выступают только такие, у которых номер не более <tex>k</tex>.
Построим эти регулярные выражения:
