Finite Automata

       An automaton with a set of states, and its “control” moves from state to state in response to external “inputs”  is called a finite automaton.    

      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, ie. 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.

  

A deterministic finite automaton (or DFA) is a deterministic automaton with a finite input alphabet and a finite number of states. It can be formally defined as a 5-tuple (Sq0F)  , where

• S is a non-empty finite set of states,
• is the alphabet (defining what set of input strings the automaton operates on),
• :SS is the transition function,
• q0S  is the starting state, and
• FS is a set of final (or accepting states).

A DFA works exactly like a general automaton: operation begins at q0  , and movement from state to state is governed by the transition function . A word is accepted exactly when a final state is reached upon reading the last (rightmost) symbol of the word.
DFAs represent regular languages, and can be used to test whether any string in is in the language it represents. Consider the following regular language over the alphabet :=ab (represented by the regular expression aa*b):

<S> <A> ::= ::= aA b|aA  

This language can be represented by the DFA with the following state diagram:

The vertex 0 is the initial state q0  , and the vertex 2 is the only state in F . Note that for every vertex there is an edge leading away from it with a label for each symbol in . This is a requirement of DFAs, which guarantees that operation is well-defined for any finite string.
If given the string aaab as input, operation of the DFA above is as follows. The first a is removed from the input string, so the edge from 0 to 1 is followed. The resulting input string is aab. For each of the next two as, the edge is followed from 1 to itself. Finally, b is read from the input string and the edge from 1 to 2 is followed. Since the input string is now , the operation of the DFA halts. Since it has halted in the accepting state 2, the string aaab is accepted as a sentence in the regular language implemented by this DFA.
Now let us trace operation on the string aaaba. Execution is as above, until state 2 is reached with a remaining in the input string. The edge from 2 to 3 is then followed and the operation of the DFA halts. Since 3 is not an accepting state for this DFA, aaaba is not accepted.

Remarks.

• A DFA can be modified to include -transitionsEpsilonTransitions. But the resulting DFA can be simulated by another DFA (without any epsilon transitions).
• Although the operation of a DFA is much easier to compute than that of a non-deterministic automaton, it is non-trivial to directly generate a DFA from a regular grammar. It is much easier to generate a non-deterministic finite automaton from the regular grammar, and then transform the non-deterministic finite automaton into a DFA.