Войти
Войти
 

Регистрация

Уже есть аккаунт?
Полная версия Пикабу

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

в

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

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

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

  •  
  • 0
  •  
5 плюсов 5 минусов

12 комментариев

nbvehbectw 
+4
 

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

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

Igorious 
0
 

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

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

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

0
 

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

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

Всё решение

JhonPreston 
-1
 

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

+2
 

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

Katzhman 
0
 

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

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

JhonPreston 
0