Description
1. Consider the following deterministic finite automaton.
-
-
-
-
-
-
b
a,b
a
1
2
a
3
-
-
-
-
-
b
-
-
Give the language accepted by this DFA.
-
(Emulate the way we express languages as sets below. Use a formal universe-constraint style.)
-
-
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).
-
-
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.)
-
Build a deterministic finite automaton that accepts the language {w ∈ {a, b}∗ : w ends with ab}.
-
-
Draw the state diagram. Use states numbered 1 through n, with the start state 1.
-
-
-
Encode the machine in our file format.
-
-
Build a deterministic finite automaton that accepts the language {w ∈ {a, b}∗ : w has length at least 4 and its third symbol is b}.
-
-
Draw the state diagram. Use states numbered 1 through n, with the start state 1.
-
-
-
Encode the machine in our file format.
-
-
(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.
