CSE322: Introduction to Formal Models in Computer Science

3

Finite automata and regular expressions; context-free grammars and pushdown automata; nondeterminism; Turing machines and the halting problem. Emphasis on understanding models and their applications and on rigorous use of basic techniques of analysis. Induction proofs, simulation, diagonalization, and reduction arguments.

CSE 321.

Michael Sipser, Introduction to the Theory of Computation, Second Edition. Thompson Course Technology, 2006

Teach students the basics of three formal models of computation: finite automata, context-free languages, and Turing machines with special emphasis on methods for manipulating and reasoning about them. Give students an idea of the value and applicability of the formal models. Give sufficient grounding in automata and formal languages to prepare for parsing in the compilers class. Languages, finite automata, regular expressions, context-free grammars, and other automata such as pushdown store machines and Turing machines. Introduction to proofs about computation models and theoretical concepts such as nondeterminism.

strings and languages: concatenation, powers, and reversal of strings regular languages: regular expressions finite automata DFAs NFAs cross product construction subset construction Kleene's theorem closure properties - union, concatenation, star, intersection, complement decision problems - emptiness, finiteness, equivalence nonregular languages optional: Myhill-Nerode Theorem minimization of DFAs pattern matching context-free languages: context-free grammars examples from real programming languages such as C++ derivation trees leftmost derivations ambiguous grammars closure properties - union, concatenation, star Chomsky normal form non-context-free languages non-closure properties: intersection, complement parsing methods top-down and bottom-up parsing efficient deterministic parsing (Cocke-Kasami-Younger algorithm) pushdown automata equivalence of PDAs and context-free grammars deterministic PDAs optional: decision problems inherently ambiguous context-free grammars Turing machines and undecidability: countability and uncountability (Cantor's proof) universal Turing machine halting problem is undecidable

3 lecture hours per week. Weekly written assignments. Midterm and final exam.

(m) knowledge of discrete mathematics

(a) an ability to apply knowledge of mathematics, science, and engineering

(c) an ability to design a computing system, component, or process to meet desired needs within realistic constraints such as economic, environmental, social, political, ethical, health and safety, manufacturability, and sustainability

(e) an ability to identify, formulate, and solve computer engineering problems

beame