Mon 30 Sept: NO CLASS

Wed 2 Oct: Test TWO

Fri 4 Oct: Push-down Automata

1. Assign 5 due Friday 10/11
2. Review of Test 2
3. Regular grammars mimic FAs. Every RHS is Term or TermVar.
4. Practice 12
5. A PDA has a stack. Example PDA for 0^n1^n

Mon 7 Oct: More PDAs

1. More PDA example: (a) Binary except $ in middle. (b) Balanced brackets
2. Practice 13 and Practice 14
3. Fact: PDAs and CFGs accept same languages (Proof omitted)
4. Chomsky Normal Form (Algorithm omitted)

Wed 9 Oct: More about Context-Free Languages

1. The Chomsky Hierarchy
2. Decison Problems
3. Closure Problems for Context-Free
4. Quiz 3

Fri 11 Oct: Asynchronous

1. Listen to someone else

Wed 16 Oct: Revision

1. Review Quiz 3 and Assign 5
2. Practice 15

Fri 18 Oct: TEST 3