CS 3156 Section C, Fall 1998
Homework 5 -- due Monday, Nov. 9

1. Prove that the language tex2html_wrap_inline25 is not context-free.

Extra credit: Prove the following: if a language L over a one-symbol alphabet is context-free, then it is regular. Hint: use pumping lemma. (Note that the claim does not remain true when L is a language over a two-symbol alphabet: tex2html_wrap_inline31 is context-free, but not regular.)

2. Which of the following languages over tex2html_wrap_inline33 are context-free? Give a context-free grammar for the languages that are context-free, and give a proof for the languages that are not context-free.

  1. tex2html_wrap_inline35
  2. tex2html_wrap_inline37
  3. tex2html_wrap_inline39
  4. tex2html_wrap_inline41
  5. tex2html_wrap_inline43

3. Problem 2.17(b), page 121 of the book. Assume 2.17(a) to be true.

4. Consider the following context-free grammar:

eqnarray20

Apply the algorithm presented in class to see whether the string aaaaa is generated by the grammar or not.