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.

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

1 Answer 1

Reset to default
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

Improve this answer
$\endgroup$
3
  • $\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, 2014 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, 2014 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, 2015 at 21:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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