Non-deterministic finite automata

Download PDF
Advertisement

Non-deterministic finite automata 

Non-deterministic finite automata have the same DFA characteristic but a slight change.

  • The total number of the alphabet should be finite.
  • A total number of strings should be finite.
  • A total number of strings should be finite.
  • It is not required that the number of transitions expecting from the states not equal to the total number of the alphabet.

Non-deterministic finite automata

Transition Graph:

Transition graph has the following characteristics,

  • A total number of states should be finite and there are some initial states and some final states.
  • The total number of the alphabet should be finite.
    Advertisement
  • In the transition graph, our transitions can be a string and also including the null string. For example, our string can be as aa, bb, ab, etc.
  • Empty transitions can also be accepted.

Transition graph

Generalize Transition Graph:

In generalize, transition graph not only the strings are allowed as well as the whole regular expression can also be written in the transition.

Generalize transition graph

Finite automata

Advertisement