QUESTIONS (a) Show that the grammar for CHAIN given below is ambiguous. (b) Find an equivalent grammar (i., one that generates the same language)...

*/

The language CHAIN consists of expressions of the following type. An expression consists of a

number of terms, with # between each pair of consecutive terms, where each term is either a string

of lower-case letters or an application of the Reverse function to such a string. Examples of such

expressions include

mala # y # Reverse(mala)

block # drive # cut # pull # hook # sweep # Reverse(sweep)

Reverse(side) # Reverse(direction) # Reverse(gear)

For lexical analysis, we wish to treat every lower-case alphabetical string as a lexeme for the token

STRING, and the word Reverse as a lexeme for the token REVERSE.