Course Specifications

CMPS 479 – Automata and Formal Languages

Coordinator: Cris Koutsougeras

Last Updated: 10/4/2007

Current Course Description: Credit 3 hours. Prerequisites: Computer Science 257 or Mathematics 223 and senior standing. Introduction to computing device capabilities through study of abstract machines and corresponding formal languages. Topics include Turing machines, recursion, Chomsky grammars, context-free languages, regular languages, and finite automata.

Minimum Topics:

  • Regular languages
  • Finite State Machines (FSM)
  • Regular expressions
  • Pumping lemma for regular languages
  • Push down automata (PDA)
  • Context free grammars and parsing
  • Normal forms (Chomsky, Greibach)
  • Equivalence of Grammars and PDAs and applications to Compilers
  • Non-determinism (both with respect to FSMs and PDAs)
  • Pumping lemma for context free languages
  • Turing Machines
  • Generalized grammars
  • Halting problem, Computability/Enumerability, Decidability
  • The Church-Turing thesis
  • Properties of language combinations (concatenation, union, intersection, quotient, etc)
  • Diagonalization

Learning Objectives: Students will be able to:

  • Discuss the concept of finite state machines.
  • Design a deterministic finite-state machine to accept a specified language.
  • Explain context-free grammars.
  • Determine a language’s location in the Chomsky hierarchy (regular sets, context-free,
  • context-sensitive, and recursively enumerable languages).
  • Prove that a language is in a specified class and that it is not in the next lower class.
  • Convert among equivalently powerful notations for a language, including among
  • DFAs, NFAs, and regular expressions, and between PDAs and CFGs.
  • Explain at least one algorithm for both top-down and bottom-up parsing.
  • Explain how a compiler can be constructed for a simple context free language
  • Distinguish the concepts of computability and decidability
  • Explain how some problems have no algorithmic solution.
  • Provide examples that illustrate the concept of uncomputability.
  • Explain the Church-Turing thesis and its significance.

Units Covered:

  • AL7. Automata theory
  • DS3. Proof techniques (3)
  • AL5. Basic computability (6)

Notes:

This course deals with the following major questions:

  • Can we define our intuitive notion of the concept of computation
  • What can be computed via mechanisms that are defined by discrete structures
  • How powerful are the various classes of discrete computing structures and what are the properties of problems that each class can handle
  • Is there a computer which can universally solve problems or are there problems that cannot be solved by discrete computing mechanisms

This course presents what we know about the notion of “computing” and mechanisms to perform computing independently of the underlying physical structure that may be used for building a computer. It revolves around fun philosophical issues of the form: can we prove or disprove the validity of the statement “I am lying”. This course explains why all the problem solving methods essentially boil down to search algorithms. The course provides essential foundation for the science of computing.