In each of the first six problems, you are given a language (or in one case two languages). In response, you are to present a DFA that accepts that language. Unless otherwise indicated, the language's alphabet is {a,b}. To present a DFA, either show a state transition graph or a table. In either case, when possible you should give meaningful names to the states.
1. L1 = { w | #a(w) ≠ 0 (mod 3) ∧ #b(w) ≥ 3 }
In words, L1 contains precisely those strings having a number of occurrences of a that is not a multiple of three and a number of occurrences of b that is at least three.
2. L2 = { w | abb is not a suffix of w }
3.
(a) L3a = { uabaaav | u,v ∈ {a,b}* }
(b) L3b = { uabaaa | u ∈ {a,b}* }
In words, L3a contains precisely those strings having abaaa as a substring, while L3b requires abaaa to be a suffix.
4. L4 = { w | aab is a substring of w but bbb is not }
5. L5 = { w | w has aa as both prefix and suffix or bb as both prefix and suffix }
Note that strings such as aa and bbb are members of L5.
6. L6 = { w ∈ {0,1}+ | f(w) ≡ 0 (mod 5) }
where f is the function that maps (non-empty) bit strings (i.e., binary numerals) to their numeric values according to the usual interpretation, which goes like this:
| f(0) | = | 0 |
| f(1) | = | 1 |
| f(w0) | = | 2·f(w) |
| f(w1) | = | 2·f(w) + 1 |
That is, L6 is the set of binary numerals that represent numbers that are multiples of five.
7. In class it was argued that a DFA M (with initial state q0) satisfies the property that L(M) is infinite iff there exist states p and r and strings x, y, and z such that
Indeed, if these conditions are satisfied, { xynz | n≥0 } ⊆ L(M)
Note: Any two, or even all three, of the states mentioned could be the same state.
Answer this closely related question:
What properties are necessary and sufficient for a DFA to have in order for its language to include infinitely many strings of even length?
The answer is very similar to what is given above, except that the parities (i.e., oddness vs. evenness) of strings x, y, and z must be considered.