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.