A tutorial on finite automata

Deterministic Finite Automata

A finite automaton, FA, provides the simplest model of a computing device. It has a central processor of finite capacity and it is based on the concept of state. It can also be given a formal mathematical definition . Finite automata are used for pattern matching in text editors, for compiler lexical analysis.

Another useful notion is the notion of nondeterministic automaton.

We can prove that deterministic finite automata, DFA, recognize the same class of languages as NDFA, i. e. they are equivalent formalisms.

It is also possible to prove that given a language L there exists a unique (up to isomorphism) minimum finite state automaton that accepts it, i.e. an automaton with a minimum set of states.

The automata in the examples are deterministic, that is, once their state and input are given, their evolution is uniquely determined.

Examples

  1. Example 1: 0and1Even
  2. Example 2: a(bb)*bc
  3. Example 3: Binary Odd Numbers
  4. Example 4: 00(1|0)*11
  5. Example 5: Even Number of b's
  6. Example 6: At Most Two Consecutive b
Back to Index