Context-Free Languages: Questions

1. Consider the following grammar with start symbol S:
   
   S -> AA
   A -> AAA
   A -> a
   A -> bA
   A -> Ab
   
   
   1. What strings can be produced by derivations of four or fewer steps?
      
   2. Give at least four distinct derivations for the string babbab.
   
   
2. Construct context-free grammars which generate each of the following languages:
   1. {wcw^R | w Î {a,b}*}
   2. {ww^R | w Î {a,b}*}
   3. {w Î {a,b}* | w = w^R}
   
   
3. Consider the following grammar with start symbol S:
   
   S -> aB
   S -> bA
   A -> a
   A -> aS
   A -> BAA
   B -> b
   B -> bS
   B -> ABB
   
   
   1. Show that the string ababba belongs to this language.
   2. Prove by induction that all strings in the language have equal numbers of a's and b's.
   
   
4. Consider the following grammar with start symbol S:
   
   S -> PVP
   P -> N
   P -> AP
   N -> cheese
   N -> Jim
   V -> ate
   A -> green
   A -> big
   
   Give a parse tree for the sentence "big Jim ate green cheese".
   
   
5. Consider the following grammar with start symbol S:
   
   S -> SS
   S -> (S)
   S -> e
   
   Show that this grammar is ambiguous by generating two different parse trees for the sentence ()(). Give an equivalent unambiguous grammar.
   
   
6. Consider the pushdown automaton with start state s, accepting state f and the following transitions:
   
   ((s,a,e),(s,a))
   ((s,b,e),(s,b))
   ((s,a,e),(f,e))
   ((f,a,a),(f,e))
   ((f,a,b),(f,e))
   ((f,b,a),(f,e))
   ((f,b,b),(f,e))
   
   Indicate whether or not each of the following strings is accepted by this PDA:
   1. a
   2. b
   3. aa
   4. ab
   5. bb
   6. aab
   7. aaa
   8. baa
   9. bab
   10. bbb
   
   
7. Construct a pushdown automaton to recognise the same language as that described by the grammar in question 5.
   
   
8. Give a context-free grammar which describes the same language as that recognised by the pushdown automaton in question 6.
   
   
9. Construct a pushdown automaton to recognise the following language:
   
   {aⁱb^jc^k | i,j,k >=0 and i=j or j=k}
   
   
10. Use the pumping lemma to show that the following languages are not context-free:
    1. {aⁱb^jc^k | i < j < k}
    2. {w Î {a,b,c}* | the number of a's is equal to the maximum of the number of b's and the number of c's}