Homework 7 (due 11/8)
CS344/444


We finished talking about regular grammars and started on push-down automata; topics for next week are context-free languages and parsing.

The final paper requirements are available.

In class, I mentioned (among many other things), John Stillwell's Road to Infinity, highly recommended


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.8, 12.1 and 12.2

2. [Regular Expression Grammar, 6pt] Write a grammar that generates all legal regular expressions over alphabet {a,b}. (Include symbols u, ε, (, ), *.)

3. [Chomsky Normal Form, 8pt] Consider the grammar

S -> ABCS | ε
A -> Aa | ε
B -> BBb | b
C -> CCCc | c

Put this grammar into Chomsky normal form, do so in steps, and show the details and results of each step:

  1. eliminate epsilon productions
  2. eliminate unit productions
  3. eliminate mixed productions
  4. eliminate long productions

4. [PDA, 10pt] Do exercise 12.1 a), b) (page 277).

5. [PDA - Acceptance conditions, 5pt] Show that if we have a PDA that accepts by empty stack alone, then the PDA can be converted to a PDA that accepts by empty stack and accepting state. Explain your general idea for the conversion and then illustrate the idea by giving an example (you can use a small PDA, two or three states are sufficient).

6. [Extra Credit] Write a PDA that accepts all strings that are not of the form ww.


Marcus Schaefer
Last updated: November 2nd, 2010.