Homework 6 (due 11/1)

We talked about Büchi automata and context-free grammars. Next week, we will finish chapter 11 and start talking about Push-down automata.

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

1. [Reading Assignment] Read Sections 11.1-11.7.

2. [Algorithmic problems, 8pt] Give a decision procedure for each of the following problems:

  1. Given an FSM M does M accept some string of odd length?
  2. Given FSMs M and N are the languages they accept disjoint?

3. [Büchi automata, 8pt] Write a Büchi automaton that accepts infinite strings over {a,b,c} that contain infinitely many as, bs, and cs.

4. [Grammars, 8pt] Consider the grammar

S -> SSS

S -> 0S0

S -> 1S1

S -> 01S01

S -> 10S10

S -> ε

a) Give a concise description of the language generated by this grammar.

b) The language contains the string 10010101. Give a derivation and parse tree for this string.

5. [Context-Free Grammars, 8pt] Write a context-free grammar that recognizes correctly parenthesized strings over (), [], and {}. E.g. {{()([]{})}} is correctly parenthesized, but (){[}] is not.

6. [Extra Credit, tricky] Let L = {ww: w in {a,b}*}. Show that the complement of L is context-free.

Marcus Schaefer
Last updated: October 26th, 2010.