Basic results from automata theory tell us that the language L = aⁿbⁿcⁿ = ∈, abc, aabbcc, aaabbbccc, . . . is not context free. It can be captured, however, using an attribute grammar. Give an underlying CFG and a set of attribute rules that associates a Boolean attribute ok with the root R of each parse tree, such that R.ok = true if and only if the string corresponding to the fringe of the tree is in L.

Transcribed Image Text:

cdr quote a b