CODEWITHSUNDEEP
algorithmlanguage-agnosticstate-machinejflap
Dusan Biga
Dusan Biga

Reputation: 63

Non-deterministic finite automata

Could someone explain why this(the automata in the picture)is a NDFA? Is it because it only has one initial state or because there are several arrows with the same symbol that arrive at the same state? I dont quite understand if one of those things define it as an NDFA? enter image description here

Upvotes: 0

Views: 391

Answers (1)

Matt Timmermans
Matt Timmermans

Reputation: 59174

It's non-deterministic because q1 has two different transitions on #.

After (#, the machine is in states q1 and q3, and will accept all of @), #@), ##@), etc.

State q3 is, however, redundant. You could just remove it to produce a DFA that accepts the same language.

Upvotes: 3

Related Questions