Я должен построить DFA, который принимаетПравильно ли это DFA?
{ш | w - это слово, кроме «aa» и «aaa»}
Правильно ли это solution? Предполагается, что состояние линии толстое должно быть конечным.
EDIT
Sry, как-то смешивают два разных упражнения. Исправленный.
EDIT 2
Вот исправленный solution (?)!
Я оставлю ответ ниже неповрежденным, так как он полезен в контексте.
С обновлением вопроса и дальнейшим обновлением предлагаемого решения мне показалось, что оно будет действительным. Отлично сработано!
========= Старое сообщение для исторических целей ===========
Важное примечание: аа подстрока ааа. Таким образом, исключая aa, вы автоматически исключаете aaa и aaaa и aaaaa. Это означает, что у вас может быть только один подряд.
Итак, всякий раз, когда вы добавляете a, вам нужно перейти в состояние accept. Всякий раз, когда вы добавляете a после этого, вам нужно перейти в состояние non accept, которое петли навсегда независимо от того, что.
Ниже приведено то, что я придумал. Я не рекомендую просто ... положить его вниз. Думать об этом. Эти проблемы очень важны в обучении, как вы думаете !!! Не портите себя!
S обозначает начальное состояние + на углу обозначает принять государству X на углу обозначает не принимает государству
B +-+ A +-+ A X-X A | B
+---|S| ---> |1| ---> |2| ------+
| +-+ +-+ X-X |
+___^ ^___B___| ^________+
"" - ends on start - okay
"B" - ends on start - okay
"A" - ends on 1 - okay
"AA" - ends on 2 - not accepted
"BAA" - Stats on S, goes to S, goes to 1, goes to 2 - not accepted.
A - перемещает вас вниз по линии к неудаче. B - сбрасывает вас. two Как в строке, и вы терпите неудачу :(
ОП пересмотрел свой вопрос с тех пор, как вы разместили это. –
Вопрос hw как представленный может быть немного неясным. Это означает, что w является словом, если оно * не содержит * подстроку 'aa' и 'aaa «Или это может означать, что это совпадение, если это не« аа »и« ааа », например, w =« aafoobar »будет соответствовать. – greatwolf