We will build an automaton for accepting words which:
- start with either
- followed by
- followed by some
as (zero or more)
- end with either
bbcb are accepted.
acaa (non-accepting state) and
bab(junk state) are not.
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$
A DFA is a 5-tuple
$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:
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.
You probably want to keep in memory at least the
accepting states and the
You should implement two functions:
buildwhich fills the
transitionmatrix. Don’t forget about the
evaluatewhich takes a
trueif the automaton accepts it, and
- start in state
- go through each
wordmoving among the automaton’s
- check if the
stateyou stopped in is
- start in state
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,
5 . Each subsequent line corresponds to one cell in the
transition matrix. Eg:
0 a 2 for $\delta(q_0, a)=q_2$.
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).
DFA accepting an even number of
λ (the empty word) are accepted.
aaa are rejected.
0 0 a 1 1 a 0
Same format as above.
aa aaaa _ a aaa
1 1 1 0 0
Same format as above,
_ stands for