12. The answer is yes. It can be obtained by starting from the set identity
The key observation is that since L 1 is finite, L 1 L 2 is finite and therefore
regular for all L 2 . The rest then follows easily from the known closures
under union and complementation.
14. By closure under reversal, L R is regular. The result then follows from
closure under concatenation.
16. Use L 1 = Σ * . Then, for any L 2 , L 1 ∪ L 2 = Σ * , which is regular. The given
statement would then imply that any L 2 is regular.
18. We can use the following construction. Find all states P such that there is a
path from the initial vertex to some element of P, and from that element to a
final state. Then make every element of P a final state.
26. Suppose G 1 = (V 1 ,T,S 1 ,P 1 ) and G 2 = (V 2 ,T,S 2 ,P 2 ). Without loss of
generality, we can assume that V 1 and V 2 are disjoint. Combine the two
grammars and
(a) Make S the new start symbol and add productions S → S 1 |S 2 .
(b) In P 1 , replace every production of the form A → x, with A ∈ V 1 and x
∈ T * , by A → xS 2 .
(c) In P 1 , replace every production of the form A → x, with A ∈ V 1 , and x
∈ T * , by A → xS 1 , S 1 → λ.
Section 4.2
1. Since by Example 4.1 L 1 – L 2 is regular, there exists a membership algorithm
for it.
2. If
, then L 1 ∪ L 2 = L 2 . Since L 1 ∪ L 2 is regular and we have an
algorithm for set equality, we also have an algorithm for set inclusion.
5. From the dfa for L, construct the dfa for L R , using the construction suggested
in Theorem 4.2. Then use the equality algorithm in Theorem 4.7.