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}$

Link to original

4. Nondeterminism

DFA as a theoretical model for programming

$-$ unusual / visual, different from conventional programming languages $+$ major concepts of imperative programming (e.g. sequences, branching, loops) can be simulated $+$ elegant, simple to use (visual), has a developed theory $+$ all pattern matching can be described $-$ limited expressive power (constant amount of memory)

Combining two automata

High-level languages typically implement things such as method calling and modularity, in this section we try to determine if we can do the same with finite automata.

Design an automaton $A$ such that $L(A)$ consits of all the strings of $a$s and $b$s that have either two consecutive $a$s or two consecutive $b$s.

Since we already have the ‘methods’ to solve the problem for $aa$s and $bb$s, we could design a ‘main program’ that would just call the given methods. One possible solution would be to combine the initial states.

$$\begin{array}{rl}L(A_3)& =\text{all the words having two consecutive }a\text{s}\\ L(A_3^{\prime })& =\text{all the words having two consecutive }b\text{s}\end{array}$$

Automaton $A$ such that $L(A)=L(A_3)\cup L(A_3^{\prime })$

digraph {
	rankdir=LR
	init[shape=point]
	node[shape=doublecircle]; r1, r2;
	node[shape=circle];
	init->s
	
	s->s [label=a]
	s->s [label=b]
	
	s->q2 [label=b]
	q2->s [label=a]
	q2->r2 [label=b]
	r2->r2 [label=a]
	r2->r2 [label=b]
	
	s->q1 [label=a]
	q1->s [label=b]
	q1->r1 [label=a]
	r1->r1 [label=b]
	r1->r1 [label=a]
}

Observe that the state transition diagram on the previous slide no longer represents a DFA:

• there is more than one $a$-arrow leaving state $s$
• there is more than one $b$-arrow leaving state $s$

We say that this automaton is nondeterministic, this is because given a state $s$ and reading $a$ from the input tape, the device has a choice to either move to state $q_1$ or $s$. In order words, the next state is not determined by the previous state and the symbol read.

Link to original

5. NFAs transition table, acceptance

Nondeterminism

Apart from having a choice in certain situations, there are other permitted features in nondeterministic finite automata (NFA):

• There can be states and symbols such that no arrow labelled by that symbol leaves thes tate in question: reading that symbol in the state the device would get stuck.
• We also allow the machine to jump from a state to another state, without ‘consuming’ any input symbol from the tape (the head doesn’t move). The allowed ‘state-jumps’ will be indicated on the state transition digrams by arrows labelled by the empty word $ϵ$.

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

NFA Transition Table

From the NFA described above, we know that the states are $s,q,r$, the input alphabet is $\{a,b\}$, the initial state is $s$ and the favourable state is $s$. We find the table:

	$a$	$b$	$ϵ$
$s$	$-$	$r$	$q$
$q$	$s$	$-$	$-$
$r$	$q,r$	$q$	$-$

This table has a few notable features:

• There can be ‘cells’ in the table containing no or more than one states.
• The table has an $ϵ$-column (for any jumps).

An NFA can be regarded as a DFA if all cells in the $ϵ$-column are empty, and in vevery other column every cell contains a single state.

Acceptance of words by NFAs

In an NFA, there can be more than one computation on an input word. Some of these may end up in a favourable state, some may not.

A word $w$ is accepted by NFA $A$ if there is a computation of $A$ on input $w$ that ends up in some favourable state.

title: There may be other bad computations.

title: Getting stuck in a favourable state may not mean acceptance. The entire word needs to be read.

In any other case, $A$ rejects the input word. So an NFA can reject an input word $w$ if every computation on $w$ is either ‘stuck’ or ends up in a non-favourable state.

Link to original

6. NFA Example 1

NFA Example 1

Given the following NFA:

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

$$baba\text{ is accepted}\leftarrow \{\begin{array}{ll}(s,baba),(q,baba)& \text{stuck}\\ (s,baba),(r,aba),(q,ba),(q,a),(s,ϵ)& \text{favourable}\end{array}$$ $$aa\text{ is accepted}\leftarrow \{\begin{array}{ll}(s,aa),(q,aa),(s,a),(q,a),(s,ϵ)& \text{favourable}\end{array}$$ $$babba\text{ is accepted}\leftarrow \{\begin{array}{ll}(s,babba),(q,babba)& \text{stuck}\\ (s,babba),(r,abba),(r,bba),(q,ba)& \text{stuck}\\ (s,babba),(r,abba),(q,bba)& \text{stuck, no more cases}\end{array}$$Link to original

7. NFA Example 2

NFA Example 2

Given the following transition table:

	$0$	$1$	$ϵ$
$s$	$s,p$	$q$	$p$
$q$	$p$	$-$	$-$
$p$	$-$	$q$	$-$

Produces the NFA:

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

$$11\text{ is rejected}\leftarrow \{\begin{array}{ll}(s,11),(q,1)& \text{stuck}\\ (s,11),(p,11),(q,1)& \text{stuck, no more}\end{array}$$ $$00\text{ is rejected}\leftarrow \{\begin{array}{ll}(s,00),(s,0),(s,ϵ)& \\ (s,00),(s,0),(s,ϵ),(p,ϵ)& \\ (s,00),(s,0),(s,ϵ)& \\ (s,00),(s,0),(p,0)& \text{stuck}\\ (s,00),(p,0)& \text{stuck}\\ (s,00),(p,00)& \text{stuck, no more}\end{array}$$ $$001\text{ is accepted}\leftarrow \{\begin{array}{ll}(s,001),(s,01),(s,1),(q,ϵ)& \text{favourable state}\\ \cdots & \end{array}$$Link to original

8. Designing NFAs

Designing NFAs

Nondeterminism can be viewed as a sort of parallel computing model, within which several processes can be running concurrently.

NDAs are much easier to design than DFAs, whatever can be done by an NDA can also be done (in a more complicated way) in a DFA. Nondeterminism does not increase computation power of finite automata.

NFAs are used in hardware / chip design:

• Given a task, NFA is designed.
• NFA is turned into a DFA.
• Resulting DFA is ‘minimised’.
• Obtained minimal DFA is hard-wired.

Pattern Matching

Revisiting 1-3. Designing DFAs > Pattern Matching.

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

	$a$	$b$	$ϵ$
$u$	$u,x$	$u$	$-$
$x$	$y$	$-$	$-$
$y$	$-$	$z$	$-$
$z$	$z$	$z$	$-$

digraph {
	rankdir=LR
	init[shape=point]
	node[shape=doublecircle]; z;
	node[shape=circle];
	init->u
	
	u->u [label=a]
	u->u [label=b]
	u->x [label=a]
	x->y [label=a]
	y->z [label=b]
	z->z [label=a]
	z->z [label=b]
}

Given the same task, it is much easier to design an NFA than a DFA for it:

• we don’t have to worry about all computations
• we need to ensure that if a word is accepted, then there is at least one ‘good’ computation for it
• if a word should be rejected, there is no ‘good’ computation for it

Link to original

9. The subset construction

Subset Construction

The Subset Construction is an algorithm that carries out a conversion from a nondeterministic automaton to its deterministic equivalent.

Equivalence of DFAs and NFAs

Given two automata $A$ and $A^{\prime }$ that accept the same language are said to be equivalent. For every NFA $A$, there is a DFA $A^{\prime }$ equivalent to $A$.

Converting NFA to DFA

Given an NFA as follows, turn it into an equivalent DFA.

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

In a DFA, we are not allowed multiple choices, being stuck or to use $ϵ$-jumps. We need to define:

• new states: named after subsets of the original NFA’s states
• new initial state: the set containing the original NFA’s initial state, plus all states that are reachable from it by some $ϵ$-jumps
• new favourable states: those subsets that contain at least one of the original NFA’s favourable states

digraph {
	init[shape=point]
	node[shape=doublecircle]; s, sq, sr, sqr;
	node[shape=circle];
	init->sq
	
	s   [label="{s}"]
	sq  [label="{s,q}"]
	sr  [label="{s,r}"]
	sqr [label="{s,q,r}"]
	
	0  [label="{}"]
	r  [label="{r}"]
	q  [label="{q}"]
	qr [label="{q,r}"]
}

The new states are named after subsets of the old states:

digraph {
	label="for each symbol x in the input alphabet"
	rankdir=LR
	P->a
	a[label="?"]
}

Where $?$ is the set of all those states that are reachable from some state in the set $P$, either by a $x$-arrow or by an $x$-arrow followed by possibly one or more $ϵ$-jumps (but not $ϵ$-jump then $x$-arrow).

In a DFA every state must have one $a$-arrow out and one $b$-arrow out. We being with the initial state an compute where two arrows go from it:

	$a$	$b$
$\{s,q\}$	$\{s,q\}$	$\{r\}$

We look at the NFA again to find that:

• from $s$ we cannot reach anything by an $a$-arrow
• from $q$ we can reach $\boxed{s}$ by an $a$-arrow
• from $q$ we can reach $\boxed{q}$ by an $a$-arrow followed by an $ϵ$-jump

Hence the $a$-arrow from state $\{s,q\}$ goes to state $\{s,q\}$ itself.

• from $s$ we can reach $\boxed{r}$ by a $b$-arrow
• from $q$ we cannot reach anything by a $b$-arrow

The $b$-arrow from state $\{s,q\}$ goes to state $\{r\}$.

Next, for every obtained new state, we compute where the $a$-arrow and the $b$-arrow goes from it. We do this until there are no newly obtained states.

	$a$	$b$
$\{s,q\}$	$\{s,q\}$	$\{r\}$
$\{r\}$	$\{q,r\}$	$\{q\}$
$\{q,r\}$	$\{s,q,r\}$	$\{q\}$
$\{q\}$	$\{s,q\}$	$\varnothing$
$\{s,q,r\}$	$\{s,q,r\}$	$\{q,r\}$
$\varnothing$	$\varnothing$	$\varnothing$

Final DFA

digraph {
	rankdir=LR
	init[shape=point]
	node[shape=doublecircle]; sq, sqr;
	node[shape=circle];
	init->sq
	
	sq  [label="{s,q}"]
	sqr [label="{s,q,r}"]
	
	0  [label="{}"]
	r  [label="{r}"]
	q  [label="{q}"]
	qr [label="{q,r}"]
	
	sq->sq   [label=a]
	sq->r    [label=b]
	r->qr    [label=a]
	r->q     [label=b]
	qr->sqr  [label=a]
	qr->q    [label=b]
	q->sq    [label=a]
    q->0     [label=b]
	sqr->sqr [label=a]
	sqr->qr  [label=b]
	0->0     [label=a]
	0->0     [label=b]
}

Link to original

10. State minimisation

State minimisation

An important field where finite automata are being used is in hardware design, some components of hardware (chips) are based on simulating DFAs.

• Given a task, an NFA is designed, since it is easier to design than a DFA.
• This NFA is turned into a DFA doing the same thing (using subset construction). The number of states of the resulting DFA may increase significantly. The worst case scenario is $\boxed{2^{\text{number of states of original NFA}}}$.
• The resulting DFA is ‘minimised’, to obtain a DFA that has the minimum possible number of states for the given task.

  title: There are various ways to do this, see recommended literature.

• Finally, obtained DFA is hard-wired.

Link to original