Рисование простого недетерминированного конечного автомата (NFA)

Как я могу нарисовать NFA (автомат) для этого вопроса?

Сначала он должен принять:

  • алфавит = х, у, г

  • L = {ш | w такой, что одно из числа вхождений x,y,z кратно трем. }

Например: {xxx, yyy, zzz, xyxyzzz, xyxyx, zyzyz...}


automaton computation-theory formal-languages
person Knaas    schedule 26.03.2012    source источник
comment
Я могу только думать об этом положении dfa. ε движется, это действительно сложно для меня. я действительно не нахожу решения сейчас   -  person Knaas    schedule 27.03.2012
comment
@Knaas: Разве это не домашнее задание? конечно похоже. Если да - пожалуйста, не удаляйте тег homework.   -  person amit    schedule 27.03.2012
comment
даже если это так, я не могу этого сделать, я не могу найти решение по этому поводу.   -  person Knaas    schedule 27.03.2012

Ответы (1)


arrow_upward
2
arrow_downward

Сначала давайте начнем с более простого вопроса:
Как бы вы нарисовали этот автомат для L' = {an | п % 3 == 0}?

Вы бы нарисовали автомат с 3 состояниями — по одному для каждого возможного модуля и перебирали бы их для каждого появления a. Принимающее состояние будет обозначено для 0.

Теперь, после установления этого - для вашей задачи вам нужно иметь 33 состояния для вашего автомата - все возможные кортежи для (x,y,z), где x, y, z находятся в {0,1,2}.

Ваша цель сейчас — понять, какой будет ваша лямда? Поскольку это ваша домашняя работа, я не буду давать полный ответ, только намек:

Если вы видите x и находитесь в состоянии (a,b,c), вы хотите перейти к (a+1 %3 ,b,c)

Также подумайте - что такое принимающие состояния? подсказка: в каком состоянии принималось упрощенное L'?

вложение: автомат для L', как описано выше.

Автомат

person amit    schedule 26.03.2012
comment
:S Мне трудно понять ваш ответ, извините за это. :/ - person Knaas; 27.03.2012
comment
@Knaas: Какую именно часть ты не понимаешь? Вы понимаете, как нарисовать автомат для упрощенного L'? - person amit; 27.03.2012
comment
@Knaas: Взгляните на редактирование - я добавил рисунок автомата для L' - как только вы это поймете - продолжайте и прочитайте, как создать автомат для более сложного L - person amit; 27.03.2012
comment
я минимизировал dfa, я преобразовал nfa в dfa. Я действительно не умею рисовать сам. я не могу решить с чего начать вы дайте мне немного информации :с - person Knaas; 27.03.2012
comment
@Knaas: я не понимаю твоего вопроса. Если у вас уже есть DFA - изменить DFA на NFA тривиально [то же самое относится и к NFA!] - person amit; 27.03.2012