CSED341 Automata and Formal Languages, Fall 2016


Announcements

Primary Textbook

Introduction to Automata Theory, Languages, and Computation, 3rd edition
(by J. E. Hopcroft, R. Motwani, and J. D. Ullman, 2006)

Lectures

Dates and Titles Topics Lecture Slides
Lecture 1
Introduction to automata
  • Overall course introduction
  • Introduction to automata

Lecture 2
Finite automata

  • Deterministis finite automata (DFA)
  • Nondeterministic finite automata (NFA)
  • Equivalence between DFA and NFA

Lecture 3
Regular languages

  • Regular expressions
  • Regular grammars
  • Properties of regular languages

Lecture 4
Context-free languages

  • Context-free grammars
  • Normal forms
  • Push-down automata
  • Properties of context-free languages

Lecture 5
Turing machines

  • Standard Turing machine
  • Variations of Turing machine
  • Universal Turing machine
  • Linear bounded automata
  • Recursively enumerable languages
  • Undecidability
  • Kolmogorov complexity