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:

- eliminate epsilon productions
- eliminate unit productions
- eliminate mixed productions
- 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.