This course is no longer offered
20242 Automata Theory and Formal Languages
Credits: 6 intermediate credits in Computer Science
Prerequisites: none
Required: Introduction to Computer Science or Introduction to Computer Science Using Pascal, Discrete Mathematics: Set Theory, Combinatorics and Logic1
Recommended: Calculus I, Linear Algebra I
This is one of a series of courses which introduces the theoretical foundations of computer science, and discusses basic mathematical problems on which computer science is based.
The course acquaints students with basic computational models, compares their computational power and discusses the basic formal language families.
Topics: Basic concepts; Deterministic finite automata; Non-deterministic finite automata and regular expressions; Properties of regular languages; Algebraic characterization of regular languages; Grammars; Abstractions and regular forms of context-free grammars; Pushdown automata; Properties of context-free languages.
1or Discrete Mathematics (20276) which is no longer offered.