CODEWITHSUNDEEP
finite-automatanon-deterministic
Nick
Nick

Reputation: 25

Nondeterministic Finite Automata construction

It feels like this should be easier than it is, but I am having an issue with it. Here is what is asked:

Construct a NFA for the following language L = {ab,ba}*. So, I understand that I can have any combination of ab or ba in the string, but do I need a dead state if say I get two a's in a row, or does it just start over? Here are the two graphs that I have: g1 g2

Are either of these correct? And since they are NFAs vs DFA do I need a lambda edge somewhere on here?

Edit: Would this third one be correct because I need two final states? g3

Upvotes: 0

Views: 1079

Answers (1)

Patrick87
Patrick87

Reputation: 28312

If you're making an NFA, you don't need dead states; you can just let the NFA crash. DFAs probably do need dead states for completeness, depending on your definitions.

Here is an NFA (q0 is the initial state and the only accepting state):

         b
      +------+
      |      |
      V  a   |    
  +->q0 ---> q1
  |   |
a |   | b
  |   V
  +--q2

To make this a DFA you can add a dead state q3 and make all transitions not otherwise defined above terminate in q3.

Upvotes: 1

Related Questions