Отхвачу сейчас лещей в виде минусов, но ребятки я горю, может кто либо сделать вот это и объяснить принцип решения -
По заданному регулярному выражению 𝛼 построить (графически) автомат 𝐴 с одним входом и одним выходом такой, что L(A)=L(a).
𝛼=((𝑎𝑏𝑐∗)∗∨(𝑎𝑐)∗)𝑑
У меня это очень давно было, так что могу ошибаться даже в понимании задания, но вроде вот так.
Принцип решения - умозрительный... Просто смотришь, какие буквы могут встречаться в слове в каком порядке, и строишь автомат. Звездочки дают циклы. Дизъюнкция - разделение на две ветки. Если не получается зациклить, чтобы не получить лишнего - разворачивай циклы и добавляй переходы дальше по d к конечному состоянию. Я хз, как еще объяснить.
Я бы объяснил, но мне лень ._.
Мы на разбор общего алгоритма обычно тратим где-то две пары; это кучу текста и пояснений писать.
Ваш, автомат, кстати, легко упрощается до такого, если на начальном этапе правильно сделать недетерминизацию—детерминизацию:
Я ниже своё решение привела. Источник - это промежуточный граф для построения автомата.
Потому что у регулярного автомата из каждой вершины должен быть выход по каждому символу алфавита.
Это не ошибочное состояние, а нераспознавание слова. В вашем понимании любое состояние, кроме конечного является ошибочным.
Лига математиков
572 поста2.4K подписчиков