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.
Solution: The states are named to convey the relevant facts about the input read so far: being in state [j,k] means that the number of a's read so far is equal to j (modulo 3) and the number of b's read so far is k (or, in the case of k=3, three or more).
|
|
2. L2 = { w | abb is not a suffix of w }
Solution: The states are named to convey what is relevant about the input read so far, which is the identity of the longest prefix of the target string (abb) that is also a suffix of the input read so far.
|
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.
Solution: The states are named to convey what is relevant about the input read so far, which is the identity the longest prefix of the target string (abaaa) that is also a suffix of the input read so far. In the case of (a), once the target string has been matched, the input string should be accepted regardless of what input follows (which explains why the state corresponding to the target string is immortal).
(a)
|
(b)
|
4. L4 = { w | aab is a substring of w but bbb is not }
Solution: If the DFA is in a state whose names is of the form [A,x], it means that (positive target string) aab already has been seen and x is the longest prefix of (negative target string) bbb that matches a suffix of the input string read so far.
|
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.
Solution: If the DFA is in a state whose name has the form [aa,x], it means that the prefix of the input string was (target string) aa and that x is the longest prefix of aa that matches a suffix of the input string read so far. A similar remark applies to states having names of the form [bb,x].
|
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.
Solution: Assuming that at least one symbol has been read and w is the portion of the input string read so far, the DFA will be in the state whose name is the decimal numeral corresponding to the value f(w) % 5.
The only reason for the states named λ and 0 being distinct is that the specification indicated that only nonempty strings could be members of L6. (Note that {0,1}+ denotes the set of all bit strings of length at least one, in contrast to {0,1}*, which also includes the empty string λ.) This is consistent with the usual convention that a numeral (binary or otherwise) must contain at least one symbol.
|
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.
Solution: To what was given, add this sixth condition:
6. Either |y| is odd or |xz| is even.
To justify this claim, consider the four possibilities regarding the parities of |y| and |xz|. What condition (6) says is that three of the four (excepting only the one in which |y| is even and |xz| is odd) ensures that L(M) contains infinitely many even-length strings.
If conditions (1) through (5) are met, but not condition (6), that would mean that (for every choice of x, y, and z that satisfy conditions (1) through (5)) |xynz| is odd for all n≥0 and thus L(M) contains only finitely many strings of even length.