Homework 8 (due 11/15)

The main results this class were the equivalence of PDAs and context-free languages, the pumping lemma for context-free languages and the CKY algorithm for parsing. Next week we will fill in some more details, talk a bit about parsing, and, time permitting, temporal logics/model checking.

The final paper requirements are available.

Submission: you can submit the homework by hardcopy in class or by sending it to me as an email.

1. [Reading Assignment] Read Sections 12.2, 12.3.1, 12.4, 12.5, 12.6, 13.1-13.5, 14.

2. [Grammar to PDA, 5pt] Convert the grammar

S -> 0S0 | T
T -> 1S1 | ε

into a PDA (accepting with empty stack and accepting state). [Follow the bottom-up or the top-down approach; include the steps of your conversion, not just the final PDA.]

3. [Language Classification, 25pt] For each of the following languages determine whether it is regular, context-free and not regular, or neither. Prove your answer, that is, if the language is regular, give a finite automaton (or regular expression), if it is context-free but not regular, give a PDA or context-free grammar and show that it is not regular. If it is not context-free, show that it isn't.

  1. {w in {a,b}*: |w| = 2n for some n > 0}  
  2. {x#y: x, y in {a,b}* and x and y are not equal}
  3. L(G), where G is the grammar defined by
    S -> SSR | aSaa | ε
  4. and R is the reversal operator.
  5. {xxRx: x in {a,b}*}, e.g. baabba
  6. {akbncm:  k + n = m}

4. [Extra Credit] Interleaving two strings of the same length means alternating the symbols of the two strings. E.g. interleaving "void" and "form" gives us "vfooirdm" (we do not interleave words of differing length). If L is a context-free language, is the language interleave(L) that consists of all legal interleavings of two words from L itself necessarily context-free?

Marcus Schaefer
Last updated: November 9th, 2010.