What are Finite Automata?

A recognizer for a language is a program that takes a string x as input and answers “yes” if x is a sentence of the language and “no” otherwise. One can compile any regular expression into a recognizer by constructing a generalized transition diagram called finite automation. Finite automation can be deterministic means that more than one transition out of a state may be possible on the same input symbol. Both automata are capable of recognizing what regular expression can denote.

Define Nondeterministic Finite Automata (NFA).

A nondeterministic finite automaton is a mathematical model consists of

  1. a set of states Q.
  2. a set of input symbols, L called the input symbols alphabet.
  3. a transition function move that maps state-symbol pairs to sets of states.
  4. a state so-called the initial or the start state.
  5. a set of states F called the accepting or final state.

An NFA can be described by a transition graph (labeled graph) where the nodes are states and the edges show the transition function. The labeled on each edge is either a symbol in the set of the alphabet or denoting an empty string. The following figure shows an NFA that recognizes the language: (10)* I (01)*

Nondeterministic Finite Automata (NFA)

This automation is nondeterministic because when it is in state-0 and the input symbol is a, it can either go to state-1 or stay in state-0.

The advantage of the transition table is that it provides fast access to the transitions of states and the disadvantage is that it can take up a lot of space.

The language defined by an NFA is the set of input strings that a particular NFA accepts.

NFA Example: NFA for 1(1 * O)*0.

Leave a Reply