next up previous
Next: Non-deterministic Finite Automata Up: Finite Automata Previous: Finite Automata

Deterministic Finite Automata

ALPHABET, STRING, LANGUAGE. We call an alphabet any finite set of symbols. Let $ \Sigma$ be an alphabet. A string or word over $ \Sigma$ is any finite sequence of symbols from $ \Sigma$. The empty string is denoted by $ \epsilon$. A language over $ \Sigma$ is any set of strings over $ \Sigma$. Note that the above definitions do not ascribe any meaning to the strings of the language.

DETERMINISTIC FINITE AUTOMATA. A deterministic finite automaton (DFA) consists of five things:

It is convenient
Figure 1: Pictorial notations for finite automata.

LANGUAGE RECOGNIZED BY A DFA. A DFA accepts an input string if when beginning the computation in the starting state, after reading the entire string, the automaton is in an accepting state.

Figure 2: Some finite automata accepting some lexical tokens.
The set of the strings recognized by a DFA $ \cal {A}$ is called the language recognized by the DFA $ \cal {A}$ and will be denoted by $ \cal {L}$($ \cal {A}$).

TRANSITION TABLE. A straightforward way to implement a DFA is to represent the transition function $ \delta$ as a transition table. This table has a row for each state s and a column for each input symbol a . The intersection of row s and column a contains $ \delta$(s, a). Figure 3 shows the transition diagram and the transition table of an automaton.

Figure 3: Transition table for a DFA.
A DFA can be easily converted to a program to look for tokens specified by it.

COMPLETE DFA. A DFA $ \cal {A}$ = ($ \Sigma$, S, s0, F,$ \delta$) is said complete if for every s $ \in$ S and for every a $ \in$ $ \Sigma$ the transition $ \delta$(s, a) is defined.

The automaton of Figure 3 is complete whereas none of the automata of Figure 2 are.

As a model for a computer program, it is desirable for a DFA to be complete. To transform a non-complete DFA $ \cal {A}$ = ($ \Sigma$, S, s0, F,$ \delta$) into a complete DFA one needs only

  1. to add a new state to S, say E (for error) and then
  2. for every (s, a) $ \in$ S×$ \Sigma$ such that $ \delta$ was not defined at this couple, define $ \delta$(s, a) = E.

DFA RECOGNIZING THE UNION OF SEVERAL LANGUAGES. Each of the four DFA in Figure 2 recognizes a simple language over the alphabet

{\Sigma} \ \ = \ \ [a \cdots z] \ \cup \ [A \cdots Z] \ \cup \ [0 \cdots 9]
\ \cup \ \{. \}

Let us denote these languages by L1, L2, L3, L4. It is desirable to build a DFA that would recognize the language L1  $ \cup$  L2  $ \cup$  L3  $ \cup$  L4. In other words, one would like to combine the four transition diagrams in Figure 2 specifying the various patterns into a single transition diagram. This is a non-trivial task. Here are some difficulties.
Figure 4: An automaton accepting L1  $ \cup$  L2  $ \cup$  L3  $ \cup$  L4 and solving the difficulties mentionned above.
N.B. From now on and for simplicity, we do not consider capital letters any more in our example (Figure 2). In other words we reduce $ \Sigma$ to the union of [a ... z], [0 ... 9] and {.}.

next up previous
Next: Non-deterministic Finite Automata Up: Finite Automata Previous: Finite Automata
Marc Moreno Maza