These are my notes from a course that I taught at Villanova in the Fall of 1996, **CSC 4710**. The textbook was *An Introduction to Formal Languages and Automata* by Peter Linz, ISBN 0-669-17342-8. I used this material again in 1999 in CSC 8510.

The course material has not changed in any significant respects, and the textbook is quite similar to *Introduction to the Theory of Computation* by Michael Sipser.

What *has* changed, however, is HTML. You may find some amusement in noticing that all the images, including the non-ASCII characters, are `.gif `

bitmaps. This is a Unicode-free set of notes! Also, I had a lot of links to external sites, almost all of which are now broken; I've removed them. Now that we have Google and Wikipedia, I don't see any need to find comparable links.

Lecture |
Topic |

1 | Introduction and review |

2 | BNF |

3 | Fundamental concepts (most important!) |

4 | DFAs and their implementation |

5 | NDFAs and their implementation |

6 | DFAs = NDFAs |

7 | Regular expressions |

8 | Regular expressions denote regular languages |

9 | Regular grammars |

10 | Closure, homomorphism |

11 | Pigeonhole principle, pumping lemma (difficult) |

- | Review for midterm |

- | Midterm exam |

12 | CFGs |

13 | Parsing and ambiguity |

14 | Pushdown automata |

15 | NPDAs & CFGs |

16 | A pumping lemma for cfgs (still difficult) |

17 | Turing machines |

18 | Universal Turing Machines and LBAs |

19 | Recursively enumerable languages |

20 | Unrestricted grammars |

21 | The Chomsky hierarchy |

22 | Undecidable problems |

23 | Church's Thesis |

24 | Complexity Theory, P and NP |

25 | Review for Final |

- | Go over homework, Q & A |

- | Final exam 5:30-7:30 |

Copyright © 1996 by David Matuszek

Last modified Feb 17, 2012