Изменения

Перейти к: навигация, поиск
м
Исправил списки, сделал хорошие угловые скобки вместо уродских
Для доказательства будем строить автоматы, допускающие регулярные языки. При этом будем использовать индукцию по номеру поколения регулярного языка.
*'''База.''' <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>L1, L2 \in Reg_n</tex>):
**<tex>L = L \cup M</tex>**<tex>L = LM</tex>**<tex>L = L^*</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>.
Построим эти регулярные выражения:
10
правок

Навигация