Each problem asks you to "present" one or more DFAs (Deterministic Finite Automata). Such a presentation should be in the form of a transition graph or a two-dimensional table describing the transition function and identifying which state is initial and which are final/accepting. (You can find examples in course web pages.) Either way, you should attempt to name each state in a manner that suggests what data/info the machine "remembers" when in that state.
In accord with Linz's notation, nc(x) (where c ∈ Σ and x ∈ Σ* for some alphabet Σ) is the number of occurrences of symbol c in string x.
1.(a) Present a DFA that accepts the language
In words, L1a contains precisely those strings over the alphabet {a,b} in which the number of occurrences of a is even.
(b) Present a DFA that accepts the language
In words, L1b contains precisely those strings over the alphabet {a,b} in which the number of occurrences of b is not a multiple of three.
(c) Apply the Cartesian product construction to your DFAs from (a) and (b) to obtain a DFA that accepts the language
| L1c | = | L1a ∩ L1b |
| = | { w ∈ {a,b}* | na(w) ≡ 0 (mod 2) ∧ nb(w) ≠ 0 (mod 3) } |
Present the resulting DFA.
(d) Offer a remark indicating how you would modify your DFA from (c) so that it accepted the union of L1a and L1b (i.e., L1a ∪ L1b) rather than the intersection. (This language's set comprehension description is the same as L1c's, except that you would replace the conjunction operator ∧ by the disjunction operator ∨.)
2. Present a DFA that accepts the language
In words, L2 contains precisely those strings over {a,b} in which the number of occurrences of a is odd and the number of occurrences of b is at least three.
3. Present a DFA that accepts the language
In words, L3 contains precisely those strings over {a,b} in which the number obtained by adding the number of occurrences of a to three times the number of occurrences of b is two more than some multiple of four.
Hint: In effect, the machine must compute the length of the input string, modulo 4, but treate each occurrence of b as though it were of length three.
4.(a) Present a DFA that accepts the language
In words, L4a contains precisely those strings over {a,b} that begin and end with different symbols.
(b) Present a DFA that accepts the language
In words, L4b contains precisely those strings over {a,b} whose first and next-to-last symbols are different.
(c) Present a DFA that accepts the language
In words, L4c contains precisely those strings over {a,b} whose second and next-to-last symbols are different.