Verifying that a grammar is strong LL(2)

Problem 19.5 of Sudkamp's Languages and Machines asks the reader to verify that the grammar

G : S' -> S##
    S  -> aSa | bSb | λ

is strong LL(2). The FIRST and FOLLOW sets for the variable S are computed using Algorithm 19.5.1 (p. 583, 3rd ed.):

FIRST(2)(S)   = {λ,aa,bb,ab,ba}

FOLLOW(2)(S)  = {##,a#,b#,aa,bb,ab,ba}

It is clear that the length-2 lookahead sets for the S rules will not partition the length-2 lookahead set for S, due to the rule S -> λ, which gives rise to the length-2 lookahead set consisting of FOLLOW(2)(S):

LA(2)(S)        = {##,a#,b#,aa,bb,ab,ba}

LA(2)(S -> aSa) = {a#,aa,ab}
LA(2)(S -> bSb) = {b#,bb,ba}
LA(2)(S -> λ)   = {##,a#,b#,aa,bb,ab,ba}

Now it is possible that I hav开发者_StackOverflow社区e made an error in the computation of the FIRST, FOLLOW, or LA(2) sets for G. However, I'm fairly confident that I have executed the algorithm correctly. In particular, I can revert to their definitions:

FIRST(2)(S)  = trunc(2)({x : S =>* x AND x IN Σ*})
             = trunc(2)({uu^R : u IN {a,b}^*})
             = {λ,aa,bb,ab,ba}

FOLLOW(2)(S) = trunc(2)({x : S' =>* uSv AND x IN FIRST(2)(v)})
             = trunc(2)({x : x IN FIRST(2)({a,b}^*{##})})
             = trunc(2)({##,a#,b#,aa,bb,ab,ba})
             = {##,a#,b#,aa,bb,ab,ba}

Now the question is: why is the grammar strong LL(2). If the length-2 lookahead sets for the S rules do not partition the length-2 lookahead set for S, then the grammar should not be strong LL(2). But I can't reach the conclusion expected by the book. What am I not understanding?

Here is a solution. The grammar G given above is not strong LL(2). To see this, recall the definition of a strong LL(k) grammar. A grammar G is LL(k) for some k > 0 if, whenever there are two leftmost derivations

S =>* u1Av1 => u1xv1 =>* uzw1          S =>* u2Av2 => u2yv2 =>* u2zw2

where ui,wi IN Σ* for i IN {1,2}, and |z| = k, then x = y. Consider the following leftmost derivations in the grammar G above:

S =>* aaSaa##  (u1 = aa, v1 = aa##)    S =>* baSab##   (u2 = ba, v2 = ab##)
  =>1 aaaa##   (x = λ)                   =>1 baaSaab## (y = aSa)
  =>* aaaA##   (z = aa, w1 = aa##)       =>* baaaab##  (z = aa, w2 = ab##)

The derivations satisfy the conditions of the definition of a strong LL(2) grammar. However, λ \= aSa, and consequently G is not strong LL(2).

Clearly we can build many leftmost derivations that demonstrate that G is not strong LL(2). But there are several other reasons that G is not strong LL(2). For instance, it is obvious that G cannot be recongized by a deterministic pushdown automata, because there is no way to determine when to begin removing elements from the stack.