Context-Free Languages: Answers
    1. The following strings can be produced: aa, aab, aba, baa

    2. 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

    1. The context-free grammar with start symbol S is as follows:

      S -> aSa
      S -> bSb
      S -> c

    2. The context-free grammar with start symbol S is as follows:

      S -> aSa
      S -> bSb
      S -> e

    3. The context-free grammar with start symbol S is as follows:

      S -> aSa
      S -> bSb
      S -> a
      S -> b
      S -> e

    1. The derivation of the string ababba is as follows:

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

    2. 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


  4. The parse tree is as follows:

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

  5. Two different parse trees are as follows:

       S               S
  / \             / \
 S   S           S   S
/|\ /|\          |  / \
(S) (S)          e S   S
  |   |            /|\ /|\
  e   e            (S) (S)
                    |   |
                    e   e
    An equivalent unambiguous grammar is as follows:

    S -> ST
    S -> e
    T -> (S)

    1. Yes
    2. No
    3. No
    4. No
    5. No
    6. Yes
    7. Yes
    8. Yes
    9. Yes
    10. No

  7. The pushdown automaton with start state s and accepting state f has the following transitions:

    ((s,(,e),(s,())
    ((s,),(),(s,e))
    ((s,e,e),(f,e))

  8. The context-free grammar with start symbol S is as follows:

    S -> aSa
    S -> aSb
    S -> bSb
    S -> bSa
    S -> a

  9. The pushdown automaton with start state s and accepting state f has the following transitions:

    ((s,e,e),(q1,e))
    ((s,e,e),(q4,e))
    ((q1,e,e),(q3,e))
    ((q1,a,e),(q1,a))
    ((q1,b,a),(q2,e))
    ((q2,b,a),(q2,e))
    ((q2,e,e),(q3,e))
    ((q3,c,e),(q3,e))
    ((q3,e,e),(f,e))
    ((q4,e,e),(f,e))
    ((q4,a,e),(q4,e))
    ((q4,b,e),(q5,b))
    ((q5,b,e),(q5,b))
    ((q5,c,b),(q6,e))
    ((q6,c,b),(q6,e))
    ((q6,e,e),(f,e))

  10. In order to show that a language is not context-free using the pumping lemma, we must show that there are strings v, w, x, y and z such that |wy| > 0 and vwkxykz is an element of the language for all k >= 0. We assume that the language is context-free and obtain a contradiction.

    1. Let s = anbn+1cn+2. s must equal vwxyz, where v, w, x, y and z satisfy the conditions above.

      If wy contains at least one a, then it can contain no c's. Therefore, vw2xy2z must contain at least n+1 a's and exactly n+2 c's, which is impossible if the string is in the language.

      If wy contains no a's, then it must contain either b or c. Therefore, vw0xy0z = vxz has either fewer than n+1 b's or fewer than n+2 c's, but in either case exactly n a's, which is impossible if the string is in the language.

    2. Let s = anbncn. s must equal vwxyz, where v, w, x, y and z satisfy the conditions above.

      If wy contains at least one a, then it can contain no c's. Therefore, vw0xy0z = vxz must contain less than n a's, but exactly n c's, which is impossible if the string is in the language.

      If wy contains no a's, then vw2xy2z contains either more than n b's or more than n c's, but exactly n a's, which is impossible if the string is in the language.