CSEN 507 Theory of Computation

Course Information

Abstract

  • The theory of computation comprises the mathematical underpinnings of computer science. It introduces three major topics: formal languages and automata theory, computability theory, and complexity theory. This course focuses on the first topic. Complexity theory classifies problems with respect to their intrinsic degree of hardness, or the amount of computational resources (in terms of space and time) required to solve them. Computability theory addresses a more fundamental issue: is a given problem solvable (by a computer) in the first place? The theory of formal languages and automata investigates mathematical models of computation, and classifies them with respect to their computational power. These models are used to answer questions and prove results in both computability and complexity theory. In addition to its foundational role, the theory of computation had had vast applications in various areas of computing. These include the specification of the syntax of programming languages, compiler construction, string processing, and cryptography.

Outline

    1. Sets, relations, and functions.
    2. Formal languages.
    3. Deterministic finite automata.
    4. Closure properties of regular languages.
    5. Nondeterministic finite automata.
    6. Regular expressions.
    7. Context-free grammars.
    8. Pushdown automata.

Objectives

  • After passing this course, students should be able to do the following:

    • Determine the membership of a given string in an intensionally defined formal language.
    • Precisely describe the language of a given finite automaton.
    • Design finite automata to recognize a given regular language.
    • Transform a nondeterministic FA into a deterministic FA.
    • Describe regular languages using regular expressions
    • Transform a regular expression into the equivalent FA.
    • Transform a FA into the equivalent regular expression.
    • Precisely describe the language generated by a given context-free grammar.
    • Design CFGs to generate a given context-free language.
    • Transform a CFG into a CFG in Chomsky normal form.
    • Precisely describe the language of a given pushdown automaton.
    • Design a PDA to recognize a given CFL.
    • Transform a CFG into the equivalent PDA.
    • Transform a PDA into the equivalent CFG.

Textbooks

  • Sipser, Michael (2006). Introduction to the Theory of Computation (2 nd edition) , Thomson Course Technology.

RenewSession