Context-Free Grammars: Answers to Exercise of 06.11.2008

   1.
         a. The following strings can be produced: aa, aab, aba, baa

         b. Four distinct derivations are as follows:

            S => AA => bAA => baA => babA => babbA => babbAb => babbab

            S => AA => AAb => Aab => Abab => Abbab => bAbbab => babbab

            S => AA => bAA => bAAb => bAbAb => bAbbAb => babbAb => babbab

            S => AA => AAb => bAAb => bAbAb => babAb => babbAb => babbab

   2.	 a. The derivation of the string ababba is as follows:

	    S => aB => abS => abaB => ababS => ababbA => ababba

         b. In order to prove this, we need to jointly prove the following:

	    All strings derived from S have the same number of a's and b's
	    All strings derived from A have one more a than b
	    All strings derived from B have one more b than a

	    Base cases: the base cases are those production rules which have 
	    no non-terminals on the right-hand side. These are as follows:

	    A -> a
	    B -> b

	    The required property follows immediately from these rules.

	    Inductive hypothesis: we assume that the required property is 
            true for S, A and B.

	    Inductive cases: we show that the required property follows from 
            the inductive hypothesis for those production rules which have 
	    non-terminals on the right-hand side

		S -> aB

	    B generates strings which have one more b than a (by the 
	    inductive hypothesis).
	    Therefore, strings generated from the right-hand side will 
            contain the same number of a's and b's

	    S -> bA

	    A generates strings which have one more b than a (by the 
	    inductive hypothesis).
	    Therefore, strings generated from the right-hand side will 
	    contain the same number of a's and b's

	    A -> aS

	    S generates strings which have the same number of a's and b's 
	    (by the inductive hypothesis).
	    Therefore, strings generated from the right-hand side will 
		contain one more a than b

	    A -> BAA

	    A generates strings which have one more a than b (by the 
	    inductive hypothesis).
	    B generates strings which have one more b than a (by the 
	    inductive hypothesis).
	    Therefore, strings generated from the right-hand side will 
	    contain one more a than b

	    B -> bS

	    S generates strings which have the same number of a's and b's 
	    (by the inductive hypothesis).
	    Therefore, strings generated from the right-hand side will 
	    contain one more b than a

	    B -> ABB

	    A generates strings which have one more a than b (by the 
	    inductive hypothesis).
	    B generates strings which have one more b than a (by the 
	    inductive hypothesis).
	    Therefore, strings generated from the right-hand side will 
	    contain one more b than a
   
            3. The parse tree is as follows:

          S
         /|\
        / | \
       P  V  P
      /|  |  |\
     / |  |  | \
    A  P ate A  P
   /   |     |   \
  /    |     |    \
big   Jim  green cheese