| Description |
Link |
Comment |
| Useful Tips on Proofs |
File |
|
| Minimizing dfas: The partition algorithm |
File |
This is a more easy and elegant way to minimize a dfa than
the one presented in the class |
| Notes on NFAs |
File |
These are some notes on NFAs and NFA - DFA equivalence |
| Notes on Regular languages, regular operations and regular expressions |
File |
Contains the proof that Regular Languages are closed under union with DFAs
(theorem 1.25, pp 45-46 of book) |
| Instructions on the exam |
Link |
|
| Slides for the course |
Link |
This is the web page of the same course taught in Resselaer Polytechnic Institute by Prof.
Mukkai S. Krishnamoorthy. Notice that he uses the symbol λ to denote the empty string
(we use the symbol ε). |
| Notes on Regular Grammars |
Link |
These are some notes on Regular Grammars. Matterial is not contained in the book |
| Software for Chapters 1-3 |
Link |
Software for experimenting with Formal Languages topics (Duke University, Durham) |
| Deterministic Turing Mashines |
File |
|
| Computable functions |
File |
New version. Some slides are added. |
| Chomsky Hierarchy and Language Operations |
File |
|
| CYK |
Link |
The CYK Algorithm. Matterial is not contained in the book |
| Complexity and O-notation |
File |
Introduction to time and space complexity. The O-notation |