20440 Automata Theory and Formal Languages 1

Credits: 4 intermediate credits in Computer Science

Prerequisites: none

Required: Introduction to Computer Science Using Java,2 Discrete Mathematics: Set Theory, Combinatorics and Graph Theory3

Recommended: Infinitesimal Calculus I, Linear Algebra I

Authors: Shmuel Zaks, Nissim Francez

This is one of a series of courses that introduces the theoretical foundations of Computer Science and discusses the mathematical problems on which Computer Science is based. It acquaints students with basic computational models, compares their computational power and discusses the basic families of formal languages.

Topics: Basic concepts; Deterministic finite automata; Non-deterministic finite automata; Regular expressions; Properties of regular languages; Algebraic characterization of regular languages; Grammars; Abstractions and normal forms of context-free grammars; Pushdown automata; Properties of context-free languages.

---

1There is some overlap in the content of this and other courses. For details, see Overlapping Courses.

2or both Introduction to Computer Science Using Java I (20453) and Introduction to Computer Science Using Java II (20454).

3or Discrete Mathematics: Set Theory, Combinatorics and Logic (20283), which is no longer offered.