Explain Finite automata(NFA & DFA)

  • We compile a regular expression into a recognizer by constructing a generalized transition diagram called a finite automata
  • A finite Automata or finite state machine is a 5-tuple(S,∑,S0,F,δ) where S is finite set of states

                ∑ is finite alphabet of input symbol

                S0 ∈ S (Initial state)

                F (set of accepting states)

                δ is a transition function

  • There are two types of finite automata,
  1. Deterministic finite automata (DFA) have for each state (circle in the diagram) exactly one edge leaving out for each symbol
  2. Nondeterministic finite automata (NFA) are the other kind. There are no restrictions on the edges leaving a state. There can be several with the same symbol as label and some edges can be labeled with ε.

Leave a Reply