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)