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, contextfree 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
 Nondeterminism (both with respect to FSMs and PDAs)
 Pumping lemma for context free languages
 Turing Machines
 Generalized grammars
 Halting problem, Computability/Enumerability, Decidability
 The ChurchTuring 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 finitestate machine to accept a specified language.
 Explain contextfree grammars.
 Determine a language’s location in the Chomsky hierarchy (regular sets, contextfree,
 contextsensitive, 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 topdown and bottomup 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 ChurchTuring 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.
