Question 0-1

Consider the following grammar.

  S ->                 (no tokens)
     | a S b S
     | b S a S

a. Give a derivation for the sentence b a a b. The tree at right is to prove to you that it is possible.
b. Give a derivation for the sentence a b a a b b.
c. Draw a parse tree for the sentence a b a b. (See part (a) for an example of how to indicate a derivation to the empty sentence.)
d. Give a succinct English description of the language that this grammar describes. This description should not simply describe the grammar, but instead the properties of the sentences in the language.

Solution

S -> b S a S
  -> b a S
  -> b a a S b S
  -> b a a b S
  -> b a a b

S -> a S b S
  -> a S b a S b S
  -> a S b a S b
  -> a S b a a S b S b
  -> a S b a a S b b
  -> a S b a a b b
  -> a b a a b b

c.
d. The language is the set of sentences of a's and b's containing an equal number of each.