Automata Theory, Computability and Formal Languages

Course website:
–www.folajimiclass.weebly.com/automata.html
Course online registration:
–www.folajimiclass.weebly.com/register.html

Lecture materials:

1. Lecture slides (downloadable below)
   
2. Course text:  Introduction To Automata Theory Languages , and Computation  by J. Hopcroft, R. Motwani and J. D. Ullman (Chapters 1-8)
   
3. Wikipedia resources: http://en.wikipedia.org/wiki/Automata_theory
   

Software:
–JFLAP: software for experimenting with formal languages topics. Downloadable at www.jflap.org/jflaptmp/
–Visual Automata Simulator: A tool for simulating, visualizing and transforming finite state automata and Turing Machines.  Downloadable at http://www.cs.usfca.edu/~jbovet/vas.html

Course Outline
•Introduction to Automata Theory 
        Readings: (1) Hopcroft, Motwani and Ullman Chapter 1 &  Chapter 2.2 
        (2)  http://en.wikipedia.org/wiki/Automata_theory

                   Download slides

•Finite State Automata
–Deterministic Finite state automata
–Nondeterministic finite state automata
          Readings: Chapter 2.3
          Download slides

•Regular Expressions
         Readings: Chapter 2.5,  & Chapter 3
         Download slides

•Properties of regular languages
       Readings: chapter 4
       Download slides

•Limitations of finite automata
      Readings: Chapter 4.1
      use the same slides as above

•DFA minimization and DFA Equivalence
     Readings: chapter 4.4.2, 4.4.3 & 4.4.4
      Use the same slides as above

•Context-free languages
     Readings: Chapters 5.1, 5.2. 5.3

•Normal forms and parsing
•Pushdown automata
•Limitations of context-free languages
•Parsers for programming languages
•Turing machines