0

Теория автоматов и формальных языков

Отхвачу сейчас лещей в виде минусов, но ребятки я горю, может кто либо сделать вот это и объяснить принцип решения -

По заданному регулярному выражению 𝛼 построить (графически) автомат 𝐴 с одним входом и одним выходом такой, что L(A)=L(a).

𝛼=((𝑎𝑏𝑐∗)∗∨(𝑎𝑐)∗)𝑑

Дубликаты не найдены

+4

У меня это очень давно было, так что могу ошибаться даже в понимании задания, но вроде вот так.

Принцип решения - умозрительный... Просто смотришь, какие буквы могут встречаться в слове в каком порядке, и строишь автомат. Звездочки дают циклы. Дизъюнкция - разделение на две ветки. Если не получается зациклить, чтобы не получить лишнего - разворачивай циклы и добавляй переходы дальше по d к конечному состоянию. Я хз, как еще объяснить.

Иллюстрация к комментарию
раскрыть ветку 6
0

Я бы объяснил, но мне лень ._.

Мы на разбор общего алгоритма обычно тратим где-то две пары; это кучу текста и пояснений писать.

Ваш, автомат, кстати, легко упрощается до такого, если на начальном этапе правильно сделать недетерминизацию—детерминизацию:

Иллюстрация к комментарию
раскрыть ветку 5
0

Но ведь это вообще не автомат, а источник.

раскрыть ветку 4
+3

Всё решение

Иллюстрация к комментарию
раскрыть ветку 1
-1

Спасибо огромное!!) Сдал))) всё супер!)

+2

Символы не отображаются

Иллюстрация к комментарию
0

Гугли "построение Томпсона".

Параграф "3.7 От регулярного выражения к НКА" в "Книге дракона".

0
Иллюстрация к комментарию
Похожие посты
Возможно, вас заинтересуют другие посты по тегам: