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

Question

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

Сначала следует принять:

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

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

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

Answer 1

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

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

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

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

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

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

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