1. Consider the following deterministic finite automaton.
b
a,b
a
1
2
a
3
b
(a) Give the language accepted by this DFA.
(Emulate the way we express languages as sets below. Use a formal universe-constraint style.)
(b) Define the 5 components of the DFA quintet (Q, Σ, δ, q0, F ) for this machine.
Q, Σ, and F should be sets. Specify the transition function by enumerating its behaviour on all inputs (e.g., δ(foo, bar) = qux).
(c) Encode this machine in our file format.
(See lecture 4 on Wednesday and a Wednesday example in even parity dfa.pdf. So delay answering this question to Wednesday.)
2. Build a deterministic finite automaton that accepts the language {w ∈ {a, b}∗ : w ends with ab}.
(a) Draw the state diagram. Use states numbered 1 through n, with the start state 1.
(b) Encode the machine in our file format.
3. Build a deterministic finite automaton that accepts the language {w ∈ {a, b}∗ : w has length at least 4 and its third symbol is b}.
(a) Draw the state diagram. Use states numbered 1 through n, with the start state 1.
(b) Encode the machine in our file format.
4. (bonus: a challenging problem for the brave few)
Build a deterministic finite automaton (DFA) that accepts the language
{w ∈ {0, 1}∗ : w begins with 1 and, when interpreted as a binary number, is a multiple of 5}
In this question, you will only draw a state diagram. Label your states intelligently to suggest their semantics, and lay it out intelligently to make it a planar graph (no edges crossing). Since I am not asking for a file format answer in this question, please be particularly clear with your diagram.
