The Theory of Computation

Bernard M.E. Moret

Addison-Wesley-Longman, 1998


Detailed Solutions

Chapter 3, Problem 25, Part 2




False. The problems is that, given L and L2, there typically exist many choices of language L' such that L=L'L2; if L is regular and L2 is finite, at least one of these choices must be regular, but not all of them need be. Since the problem tells us that all three languages are given, an affirmative answer would require us to prove that, for any choice of the three languages such that the equality holds and such that L is regular and L2 is finite, then L' must be regular -- and we can find counterexamples.

To get a regular L', we can run the machine for L until the input runs out, then start guessing a suffix and run it both through M -- continuing the computation -- and through a machine for L2 -- starting from the start state. If both machines accept together at any stage, we accept the input string. Since we cannot really run a machine until the input runs out, we use epsilon transitions instead. Given a DFA M for L, we can build an NFA M' for L1 as follows: M' will have a copy of M (with all states made non-accepting) and an epsilon transition from each state q of M to the start of a new submachine, call it M'q; this new submachine makes only epsilon transitions and combines M (started in state q) and the machine for L2, started in its start state, running them effectively in parallel. Each M'q can only make a finite number of epsilon transitions because the language L2 is finite; any state of M'q in which both the copy of M and the copy of the machine for L2 accept is an accepting state of M'. Thus, in order to accept an input string, M' must make use of one of its epsilon transitions (otherwise it stays within its copy of M, which has no accepting state), but it can only make such a transition when it has run out of input, because it will enter a submachine that will not process any input on the way to any accepting state -- any further input will cause rejection. Moreover, from this point, both the ``continuing copy'' of M and the machine for L2 must run together and accept at the same time, i.e., M' must guess a suffix for its input that belongs to L2 and that, when concatenated to its input, belongs to L.

As a counterexample (on a one-symbol alphabet, no less), let L1={0k | k>2 and not a prime} and let L2={epsilon,0}. Thus L1 is not regular and L2 is finite. Note that L=L1 L2 now consists of all strings of 0s whose length is either a non-prime or a non-prime plus 1. But that is all strings of 0s (of at least 4 characters), since any prime beyond 3 is just some non-prime plus 1. Thus L={0k | k>3} is regular and we have a counterexample. But note that we could have chosen L'=L and still have had L=L'L2.