9. Given two linear grammars G 1 = (V 1 ,T,S 1 ,P 1 ) and G 2 = (V 2 ,T,S 2 ,P 2 ) with
,
form
the
combined
grammar
. Then is linear and
.
To show that linear languages are not closed under concatenation, take the
linear language L = {a n b n : n ≥ 1}. The language L 2 is not linear, as can be
shown by an application of the pumping lemma.
13. Let G 1 = (V 1 ,T,S 1 ,P 1 ) be a linear grammar for L 1 and let G 2 = (V 2 ,T,S 2 ,P 2 )
be a left-linear grammar for L 2 . Construct a grammar from G 2 by
replacing every production of the form V → x, x ∈ T * with V → S 1 x.
Combine grammars G 1 and , choosing S 2 as a start symbol. It can then be
shown that in this grammar
if and only if u ∈ L 1 and w ∈ L 2 .
15. The languages L 1 = {a n b n c m } and L 2 = {a n b m c m } are both unambiguous.
But their intersection is never context-free.
21. λ ∈ L(G) if and only if S is nullable.
Chapter 9
Section 9.1
2. A three-state solution that scans the entire input is
with F = {q 2 }.
It is also possible to get a two-state solution by just examining the first
symbol and ignoring the rest of the input, for example,