# DFA accepter

We will build an automaton for accepting words which:

• start with either a or bb
• followed by c
• followed by some as (zero or more)
• end with either b or c

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:

• build which fills the transition matrix. Don’t forget about the junk state.
• evaluate which takes a word and returns true if the automaton accepts it, and false otherwise.
• start in state 0,
• go through each symbol in word moving among the automaton’s states accordingly
• check if the state you stopped in is accepting

## 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 λ.