Изменения

Перейти к: навигация, поиск

Участница:Наталья Юльцова

2 байта добавлено, 00:34, 8 января 2021
Преобразование регулярного выражения в НКА
===Преобразование регулярного выражения в НКА===
[[Файл:базис.png|100px|thumb|right|рис. 1. a. <tex>\varepsilon</tex> б. <tex>\varnothing</tex> в. <tex>a</tex>]] [[Файл:RegToAut.png|200px|thumb|right|рис. 2. Индуктивный шаг переход преобразования регулярного выражения в НКА]]
Преобразование проводится структурной индукцией по выражению <tex>R</tex>, следуя рекурсивному определению [[Регулярные языки: два определения и их эквивалентность| регулярных выражений]]. Необходимо рекурсивно "спуститься" вглубь языка <tex>L(R)</tex>, дойдя до нулевого уровня - <tex>R_0</tex>. Автоматы, распознающие <tex>L(R_0)</tex> представлены на рис. 1, это базис. Далее строится выражение <tex>\mathrm{R_{i+1}}</tex>, пока <tex>\mathrm{R_{i}} \ne R</tex> следующим образом:
Анонимный участник

Навигация