Уменьшение DFA до NFA

Question

Я пытаюсь выяснить проблему, когда я должен нарисовать NFA для данного языка.

Язык { w | the final five symbols of w include two a's and three b's }.

Я считаю, что у меня это как DFA, и я не уверен, есть ли более сокращенная версия. Если бы кто-нибудь мог взглянуть, что было бы очень полезно. Я чувствую, что его можно свести к довольно маленькому NFA.

Answer 1

Прежде всего, что у вас там не DFA; состояние a явно недетерминирован:

• с a вы можете пойти как a и b
• с b вы можете получили как к a и s

Во-вторых, поскольку в FSA вас может только считаться с состояниями (нет стека), вы должны отслеживать, сколько из каждого символа вы видели в последних 5 символах в пространстве состояний. Просто подумайте о том, сколько разных комбинаций вам нужно, и тогда переходы будут очевидны. Это самая маленькая NFA, с которой вы можете решить эту задачу.