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.