CS 302 Formal Languages and Automata Theory

Course Syllabus

 

 

  1. Course Overview
  2. Basic Concepts
    1. Languages
    2. Grammars
    3. Automata
    4. Applications
  3. Finite Automata
    1. Deterministic  Finite State Acceptors
    2. Nondeterminism, Nondeterministic Finite State Acceptors and their equivalence to Deterministic FSA
    3. State Minimization
  4. Regular Languages and Grammars
    1. Regular Expressions
    2. Relationships between Regular languages and Regular Expressions
    3. Relationship between  Finite State Acceptors and Regular Expressions
    4. Regular Grammars
    5. Applications of Regular Languages
    6. Applications of Regular Expressions: Using Regular Expressions in PERL.
  5. Properties of Regular Languages
    1. Closure properties
    2. Elementary questions on regular languages
    3. Identifying nonregular languages 
  1. Context-Free Grammars
    1. Overview
    2. Parsing and Ambiguity
    3. Normal Forms
  2. Pushdown Automata
    1. Deterministic and non-deterministic pushdown automata
    2. Relationship between pushdown automata and context free languages
  3. Properties of Context-free Languages
    1. Closure Properties
    2. Pumping Lemma for CFLs
    3. Decidability Properties
  4. Turing Machines

 

  1. Hierarchy  of Languages
    1. Recursive and Recursively Enumerable Sets
    2. Chomsky Hierarchy
  2. Introduction to Computability and Decidability