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:
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
–www.folajimiclass.weebly.com/automata.html
Course online registration:
–www.folajimiclass.weebly.com/register.html
Lecture materials:
- Lecture slides (downloadable below)
- Course text: Introduction To Automata Theory Languages , and Computation by J. Hopcroft, R. Motwani and J. D. Ullman (Chapters 1-8)
- 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