DFA accepter
We will build an automaton for accepting words which:
 start with either
a
orbb
 followed by
c
 followed by some
a
s (zero or more)  end with either
b
orc
Examples: acaaab
and bbcb
are accepted. acaa
(nonaccepting state) and bab
(junk state) are not.
Configuration
The automaton’s diagram can look like:
A more compact form of describing it would be $(abb)ca^n(bc), \ n \ge 0$
Formal Description
A DFA is a 5tuple
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 outbound 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:
build
which fills thetransition
matrix. Don’t forget about thejunk
state.evaluate
which takes aword
and returnstrue
if the automaton accepts it, andfalse
otherwise. start in state
0
,  go through each
symbol
inword
moving among the automaton’sstates
accordingly  check if the
state
you 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 a
s:
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 λ
.