Finite Automata


A recognizer for a language is a program that takes a string x as an 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 a finite automation.

A finite automation can be deterministic means that more than one transition out of a state may be possible on a same input symbol.

Both automata are capable of recognizing what regular expression can denote.