Deterministic Finite Automata

Formal definition

The automata we have discussed so far are all deterministic in that there is no ambiguity about which edge to follow from each state. Deterministic finite automata are also easy to program; we simply need have a case for each state, and inside each case, we choose the target state corresponding to the current input symbol. In the next section, we’ll see how nondeterministic finite automata can also be useful.

A deterministic finite automaton (DFA) is a finite state machine consisting of the following:

• $Q$, a set of states, one of which is the initial (or start) state, and a subset of which are final (or accepting) states.
• $\Sigma$, an alphabet of valid input symbols.
• $\delta:Q \times \Sigma \rightarrow Q$, a transition function which, given a state and input symbol, determines the next state of the machine.

The definition above is merely a mathematical reformulation of what we already understood a DFA to be. The transition function, $\delta$, represents the transitions/edges in the machine. The subset of $Q$ comprising the final states can be empty in the case of machines that produce an output string instead of a yes-or-no result. There must be exactly one transition out of every state for each symbol in the alphabet of the DFA.

Remember: There can only be one transition out of every state for each symbol in the alphabet of the DFA.

DFA accepting strings ending with $b$

To illustrate the application of the formal definition of a DFA, consider the DFA in the figure below, which accepts the language $L$ that contains all strings over the alphabet $\Sigma=\{a,b\}$ that end with the symbol $b$. We can write this language as $L = \{\textrm{All strings that end with }b\}$.

Every time we read a $b$, for all we know it could be the last symbol in the input string, so we move to the accepting state $q_1$; otherwise, we move to state $q_0$. Therefore, the formal definition for this DFA is:

• $Q=\{q_0,q_1\}$, where $q_0$ is the initial state and

...