EXERCISES ON GRAMMAR



 1. (a)  Characterize the language (set of strings) generated by the grammar:

            S := Ab
            A := bBa
            B := Ac
            A := b

    (b)  Is the language context-free?


 2. Give the parse tree that shows why a = b is an "expression" in C.

 3. Consider the grammar:

            S := Ab
            A := bBa
            B := Ac
            Aca := bA
            A := b

    Which of the following strings is not in the language generated by
    this grammar?

            bb  bbcab  bbbcacab  bbbbbbbb  bbbcacacacab  bbbbbcacab


There are many additional grammar exercises in "Notes on Formal
Languages".