Problem Set 9
DFAs
1 DFA to Language
Determine whether or not the following are valid DFA definitions. If the DFA is valid, what is the language of the DFA?
1.1
Solution
Not valid - the top state has no outgoing 0 transition.
1.2
Solution
Every 0 is followed by a 1.1.3
Solution
Doesn’t contain 10
2 Language to DFA
2.1
Find a DFA/NFA for the following languages:
\(L_1 = \{w \in \{0,1\}^* : w \text{ is a binary representation of a multiple of 3}\}\). Find a DFA for \(L_1\).
\(L_2 = \{w \in \{0,1\}^* : \text{every 1 is preceeded by at least two zeros }\}\).
\(L_3 = \{w \in \{0,1\}^* : \text{every 1 is preceeded by at exactly two zeros }\}\).
\(L_4 = \{w \in \{0,1\}^* : \text{every 1 is preceeded by at most two zeros }\}\).
\(L_5 = \{w \in \{0,1\}^* : \text{w contains neither 01 nor 10}\}\).