DFA accepter
We will build an automaton for accepting words which:
- start with either
aorbb - followed by
c - followed by some
as (zero or more) - end with either
borc
Examples: acaaab and bbcb are accepted. acaa (non-accepting state) and bab(junk state) are not.
Configuration
The automaton’s diagram can look like:
A more compact form of describing it would be $(a|bb)ca^n(b|c), \ n \ge 0$
Formal Description
A DFA is a 5-tuple
Where:
-
$Q$ is the set of states. In our case, $Q = \lbrace q_0, q_1, q_2, q_3, q_4, q_5 \rbrace$
-
$q0 \in Q$ is the starting state
-
$F \subset Q$ is the set of final/accepting states. In our case, $F = \lbrace q_4, q_5 \rbrace$
-
$\Sigma$ is the alphabet, a set of symbols. In our case, $\Sigma = \lbrace a, b, c \rbrace$
-
$\delta:Q \times \Sigma \rightarrow Q$ is the transition function. $\delta(q, x)=q’$ tells us that when we are in state $q$ and we read the symbol $x$, we move in state $q’$. In our case:
It’s useful to see it as a table, where the first column is the current state and the first column is the symbol we read:
| $\delta$ | a | b | c |
|---|---|---|---|
| $\bf{q_0}$ | $q_2$ | $q_1$ | |
| $\bf{q_1}$ | $q_2$ | ||
| $\bf{q_2}$ | $q_3$ | ||
| $\bf{q_3}$ | $q_3$ | $q_4$ | $q_5$ |
| $\bf{q_4}$ | |||
| $\bf{q_5}$ |
Some cells are left blank, for example $(q_0, c)$. That is because we have no transition from $q_0$ to $c$. Any missing transition can be thought as going into a junk state. It is not accepting and has no out-bound transitions so we immediately reject.
Implementation
You probably want to keep in memory at least the accepting states and the transition matrix.
You should implement two functions:
buildwhich fills thetransitionmatrix. Don’t forget about thejunkstate.evaluatewhich takes awordand returnstrueif the automaton accepts it, andfalseotherwise.- start in state
0, - go through each
symbolinwordmoving among the automaton’sstatesaccordingly - check if the
stateyou stopped in isaccepting
- start in state
IO
Input DFA.definition
4 5
0 a 2
0 b 1
1 b 2
2 c 3
3 a 3
3 b 4
3 c 5
The first line lists the accepting states. In our case, 4 and 5 . Each subsequent line corresponds to one cell in the transition matrix. Eg: 0 a 2 for $\delta(q_0, a)=q_2$.
Input DFA.tests
acaaab
bbcb
acaa
bab
1
1
0
0
Each line contains one word to test your automaton on and its expected output (1 for accept, 0 for reject).
Another DFA
DFA accepting an even number of as:
Examples: aa, aaaa, λ (the empty word) are accepted. a, aaa are rejected.
Matrix:
| $\delta$ | a |
|---|---|
| $\bf{q_0}$ | $q_1$ |
| $\bf{q_1}$ | $q_0$ |
IO
Input DFA2.definition
0
0 a 1
1 a 0
Same format as above.
Input DFA2.tests
aa
aaaa
_
a
aaa
1
1
1
0
0
Same format as above, _ stands for λ.