# This is an archived page and may be obsolete; the current pages are at http://www.iit.edu/csl/cs

# CS 532: Formal Languages

## Objectives

- This course discusses the formal modeling of computation through the mechanism of languages, which are sets of strings satisfying certain properties.
- The properties will help classify the languages into the various categories e.g. regular languages, context-free languages etc.
- Examples of the usage of these classes (categories) can be found in pattern matching, programming languages etc.
- Corresponding machine models will also be studied.
- Computability and complexity issues related to the various models will also be discussed.

## Prerequisites

- CS 430 or consent of instructor.

## Syllabus

- Regular Languages and Finite Automata
- Formal definitions of automata
- Formal definition of regular expressions and equivalence with automata
- Non-deterministic FA and their equivalence to deterministic FA
- Pumping Lemma to show that a language is not regular

- Context-Free Languages and Push-down Automata
- Formal definition of context-free grammars
- Normal forms
- Formal definition of push-down automata and equivalence with context-free grammars
- Pumping lemma to show that a language is not context-free

- Turing Machines
- Formal definition of a Turing machine
- Various models of TM's and their equivalence

- Decidability and Undecidability
- The Halting problem
- Undecidable problems in language models.
- Reducibility

- Time Complexity of Turing Machine Computations
- The classes P and NP
- NP-Completeness
- Polynomial reducibility

Edited March 2006 (html, css checks)