Note that this assignment is due on the day we come back from spring break. Also, Problem Set 4 will be due less that three weeks after that. So you might want to finish, or come close to finishing, these problems before the break.  

1. Apply the pumping lemma to each of the languages below to show that they are not regular.
   1. { 0^p1^q | p ≥ q}
   2. { 10^p1^q | p ≤ q}
    

2. Let Σ be the alphabet {0,1,.}
   Let L₁ be the language of strings over Σ that contain at most one dot.
   Let L₂ be the language of strings over Σ that are nonempty and do not begin with a dot.
   1. Find a 2-state DFA (not counting any dead state) that recognizes L₁.
   2. Find a 2-state DFA (not counting any dead state) that recognizes L₂.
   3. Use the construction of Theorem 4.8 of the text to find a DFA recognizing the set of strings over Σ that contain at most one dot but don't begin with a dot.

    

3. Find a CFG that generates L(r), where r is the regular expression 0(0+1)*1 + 1(0+1)*0.

    

4. Let L be the language generated by adding the rule F → [E] to the grammar of Figure 5.19 on p. 211 of the text. Assume that the term delimiters refers only to parentheses and brackets. Let L' be the subset of L consisting of those strings of L where
   1. the outermost delimiters are all parentheses
   2. the delimiters most closely enclosing parentheses are all brackets, and
   3. the delimiters most closely enclosing brackets are always parentheses.

   So for example, the strings ( a * [ b + c ] ) and
   ( a + b ) * ( a + b * [ a + b * ( a + b ) ] ) and
   b + ( a * [ b + a ] * [ a + a ] ) are in L', while the strings [ a * ( b + c ) ] and
   ( a * ( b + c ) ) and
   a + b * ( a + b * [ a + b * [ a + b ] ] ) are not in L'

   Find a CFG that generates L'.

   Hint: Let E be a nonterminal symbol that yields expressions satisfying conditions (2) and (3) whose outermost delimiters are all parentheses, and let E' be a nonterminal symbol that yields expressions satisfying conditions (2) and (3) whose outermost delimiters are all brackets.