0
$\begingroup$

I am just beginning to learn computation theory. I wrote up a non-deterministic finite automata that accepts strings that contain the substring "abba":

My NFA

I tried to convert it to a DFA by putting together sets of states in the NFA to be states of the DFA:My DFA

However, I just realized that my DFA doesn't accept strings such as "abbaa" that do not end in "abba." That means that my methodology was wrong. Why? I thought it would make sense to combine states of the NFA to make states of the DFA.

$\endgroup$

migrated from cstheory.stackexchange.com Sep 16 '12 at 6:05

This question came from our site for theoretical computer scientists and researchers in related fields.

  • 3
    $\begingroup$ First, make sure the NFA works (it only accepts strings that end with "abba") $\endgroup$ – Ran G. Sep 16 '12 at 11:07
12
$\begingroup$

Your methodology for creating the DFA from the NFA is fine. The problem is that you started with the wrong NFA (you'll notice that your NFA doesn't accept abbaa either). Try this one instead: enter image description here

$\endgroup$
  • $\begingroup$ How could I say that "NFA doesn't accept abbaa either" since from state 5 transition for a is not defined we remain at state 5 itself and it is a final state? $\endgroup$ – user5507 Feb 13 '14 at 2:21
  • 1
    $\begingroup$ @user5507, if a transition for a symbol is undefined at a particular state, the automata doesn't stay in that state if it sees that symbol, it changes to "no state". I.e. if there's no transition, it gets stuck/automatically rejects. $\endgroup$ – Luke Mathieson Feb 13 '14 at 12:47
  • $\begingroup$ @user5507 It is find to define the final state as "if transition undefined stay accepted", but then, your transitions from {1,2,5} should always contains a 5. $\endgroup$ – Earth Engine May 21 '15 at 21:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.