Deterministic Finite Automaton

A deterministic finite (state) automaton (DFA) is one of the weakest model of computation. It is ‘memoryless’, i.e. it cannot store past states, and can only read an input string. It changes its states in a deterministic way i.e. it always takes the same computation path for the same input.

%%🖋 Edit in Excalidraw, and the dark exported image%%

A more formal way of defining determinism is that the DFA only has one possible move at every ‘step’.

Definition §

Deterministic Finite Automata (DFA) ^definition-dfa

A DFA $D$ is defined as a 5-tuple:

$$D=(\Sigma ,Q,q_0,\delta ,F)$$

• An input alphabet, $\Sigma$
• A set of states, $Q=\{q_1,q_2,\dots \}$
• An initial state, $q_0\in Q$
• A state transition function, $\delta$ which takes the current state ($q_{cur}$) and the next character of the input string $(a)$, and returns another state $q_{next}$: $\delta :Q\times \Sigma \to Q\delta (q_{cur},a)=q_{next}$
• A set of accept states, $F\subseteq Q$

Behaviour §

• A DFA always halts, or finishes processing, for any given input finite-length input string.
• If a DFA gets a character and doesn’t know what to do, it halts and rejects the character (as a ‘catch-all’)

Connection To Regular Languages §

Recall the definition of a regular language:

Another way to interpret this is that, given a DFA $M$, there are set of strings (a regular language) that $M$ accepts.

For example, take the DFA below:

%%🖋 Edit in Excalidraw, and the dark exported image%%

The DFA $M$ only accepts strings that contain any number of zeros. This is because it does contain transitions that require other inputs, so if it received a 1, it would not know what to do, and by default, rejects the string/word. That is:

$$L(M)=\{ϵ,0,00,000,\dots \}=0^{\ast }$$

where $0^{\ast }$ is the Kleene star operation applied on $0$

The corresponding regular language is hence $0\ast$.

Minimal DFAs §

See Minimal DFA

Examples §

1: State diagram of a simple DFA

Find the formal definition ($\Sigma ,Q,F,q_0$) for the state diagram for the DFA $M$ below. Also include the set of accepted strings

Solution

The specifications are given below (the transition function isn’t required here):

• $\Sigma =\{a\}$
• $Q=\{1,2\}$
• $q_0=1$
• $F=\{2\}$

$M$ accepts strings only containing $a$, but it also has the restriction that these strings must be odd length (even length strings causes it to switch from 1 to 2 back to 1). That is:

$$L(M)=\{a,aaa,aaaaa,\dots \}=a^{2k+1},k\in \mathbb{N}$$

2: Another DFA state diagram

Find the formal definition ($\Sigma ,Q,F,q_0$) for the state diagram for the DFA $M$ below. Also include the set of accepted strings %%🖋 Edit in Excalidraw, and the dark exported image%%

Solution

The specifications are given below (the transition function isn’t required here):

• $\Sigma =\{0,1\}$
• $Q=\{q_0,q_1,q_2\}$
• $q_0=q_0$
• $F=\{q_0\}$

$M$ accepts strings from the following regular language:

$$L(M)=\{ϵ,0^{\ast },(10{)}^{\ast },(111{)}^{\ast },(110{)}^{\ast },(10111{)}^{\ast },(10110{)}^{\ast },\dots \}$$