1-3. Designing DFAs

Designing DFAs

So far we have discussed how to determine the language of a DFA:

$$\begin{array}{rl}A& ⇝L(A)\\ \text{program}& ⇝\text{specification}\end{array}$$

We want to also perform the reverse, given a language $L$, design a DFA $A$ such that the language $L(A)$ of $A$ is $L$.

$$\begin{array}{rl}L& ⇝A\text{ with }L(A)=L\\ \text{specification}& ⇝\text{program}\end{array}$$

Example Task 1

Design a DFA $A$ such that $L(A)$ consists of all the strings of $0$s and $1$s ending with $11$.

1. Determine what to remember about the input string, while the head is reading through it, from left to right.
2. Add the transitions telling how the possibilities rearrange, and select the initial state and the favourable states.
3. Test the automaton.

It is sufficient to remember three ‘states’ of the string read so far:

• The string does not end in $1$. (it is either $ϵ$ or ends in $0$) $⇝$ initial state $s$ (waiting for $11$)
• String is $1$ or ends in $01$. $⇝$ $q$ (waiting for $1$)
• String ends in $11$. $⇝$ favourable state $p$

digraph {
	rankdir=LR
	init[shape=point]
	node[shape=doublecircle]; p;
	node[shape=circle];
	init->s
	
	s->s [label=0]
	s->q [label=1]
	q->s [label=0]
	q->p [label=1]
	p->s [label=0]
	p->p [label=1]
}

Example Task 2

Design a DFA $A$ such that $L(A)$ consists of all the strings of $\alpha$ and $\beta$ whose length is divisible by $3$. Consider that:

• $s=3n$
• $p=3n+1$
• $q=3n+2$

digraph {
	rankdir=LR
	init[shape=point]
	node[shape=doublecircle]; s;
	node[shape=circle];
	init->s
	
	s->s [label="0,3,6,9"]
	p->p [label="0,3,6,9"]
	q->q [label="0,3,6,9"]
	s->p [label="1,4,7"]
	p->q [label="1,4,7"]
	q->s [label="1,4,7"]
	p->s [label="2,5,8"]
	p->q [label="2,5,8"]
	q->s [label="2,5,8"]
}

$$L(A_6)=\text{all strings of digits that as a decimal number is divisible by }3$$

	$\alpha$	$\beta$
$q_{3n}$	$q_{3n+1}$	$q_{3n+1}$
$q_{3n+1}$	$q_{3n+2}$	$q_{3n+2}$
$q_{3n+2}$	$q_{3n}$	$q_{3n}$

Pattern Matching

Design a DFA $A$ such that $L(A)$ consists of all the strings of $a$s and $b$s that contain $\boxed{aab}$ as a substring.

digraph {
	rankdir=LR
	init[shape=point]
	node[shape=doublecircle]; aab;
	node[shape=circle];
	init->s
	
	s->s [label=b]
	s->a [label=a]
	a->s [label=b]
	
	a->aa [label=a]
	
	aa->aa [label=a]
	aa->aab [label=b]
	
	aab->aab [label=a]
	aab->aab [label=b]
}

	$a$	$b$
$s$	$q_a$	$s$
$q_a$	$q_{aa}$	$s$
$q_{aa}$	$q_{aa}$	$q_{aab}$
$q_{aab}$	$q_{aab}$	$q_{aab}$