This is almost an s-grammar. As long as the currently scanned symbol is a,
we must apply S → aSc; if it is b, we must use S → S 1 ; if it is c, we can
only use S → λ. The grammar is LL(1).
Chapter 8
Section 8.1
3. Take w = a m b m b m a m a m b m . The adversary now has several choices that have to
be considered. If, for example, v = a k and y = a 1 , with v and y located in the
prefix a m , then
which is not in L. There are a number of other possible choices, but in all
cases the string can be pumped out of the language.
7. (a) Use the pumping lemma. Given m, pick
. The only choice of v
and y that needs any serious examination is v = a k and y = b l , with k and l
nonzero. Suppose that l = 1. Then choose i = 2, so that w 2 has m 2 + k a’s and
m + 1 b’s. But
so w 2 is not in the language. Similar arguments hold also for l > 1.
Therefore, the language cannot be context-free.
(f) Given m, choose w = a m b m+1 c m+2 , which is easily pumped out of the
language.
8. (b) The language is not context-free. Use the pumping lemma with w =
a m b m a m b m and examine various choices of v and y.
10. Perhaps surprisingly, this language is context-free. Construct an npda that
counts to some value k (by putting k tokens on the stack) and remembers
the kth symbol. It then examines the kth symbol in w2. If this does not
match the remembered symbol, the string is accepted. If w ∈ L, there must
we must apply S → aSc; if it is b, we must use S → S 1 ; if it is c, we can
only use S → λ. The grammar is LL(1).
Chapter 8
Section 8.1
3. Take w = a m b m b m a m a m b m . The adversary now has several choices that have to
be considered. If, for example, v = a k and y = a 1 , with v and y located in the
prefix a m , then
which is not in L. There are a number of other possible choices, but in all
cases the string can be pumped out of the language.
7. (a) Use the pumping lemma. Given m, pick
. The only choice of v
and y that needs any serious examination is v = a k and y = b l , with k and l
nonzero. Suppose that l = 1. Then choose i = 2, so that w 2 has m 2 + k a’s and
m + 1 b’s. But
so w 2 is not in the language. Similar arguments hold also for l > 1.
Therefore, the language cannot be context-free.
(f) Given m, choose w = a m b m+1 c m+2 , which is easily pumped out of the
language.
8. (b) The language is not context-free. Use the pumping lemma with w =
a m b m a m b m and examine various choices of v and y.
10. Perhaps surprisingly, this language is context-free. Construct an npda that
counts to some value k (by putting k tokens on the stack) and remembers
the kth symbol. It then examines the kth symbol in w2. If this does not
match the remembered symbol, the string is accepted. If w ∈ L, there must