New Building Website

CSA 473/573 Automata, Formal Languages, & Computability (3 credits)

 

Typically offered during the fall semester.

Catalog description:

Regular expressions. Closure properties. Sequential machines and finite state transducers. State minimization. Chomsky hierarchy grammars, pushdown acceptors and linear bounded automata. Closure properties of algorithms on grammars. Turing machine as acceptor and transducer. Universal machine. Computable and noncomputable functions. Halting problem.

 

Prerequisites:

CSA274 / CSA606 or equivalent, and Discrete Math (MTH 231).


Course Objectives:

  • To learn the fundamental principles which underlie Computer Science.
  • Computability
    • To understand some of the basics of the theory of computation.
    • To see that some functions are not computable.
  • Formal Languages.
    • To develop some knowledge of the theory of formal languages.
    • To develop some skill at the manipulation and construction of formal grammars.
    • To understand the hierarchy of languages and grammars, and to understand the power and limitations of each.
  • Automata.
    • To understand some of the models of computation: Turning machines, mu recursive functions.
    • To understand how Church's Thesis relates algorithms to these models of computation.
    • To investigate many of the automata which are used as models of computation, and how they correspond to formal languages and grammars.
  • To begin to perceive the ways in which the theory of computation, the theory of automata, and formal languages relate to programming and software.

Learning Outcomes:

CSA 473.1: To be able to design and trace automata and grammars.
CSA 473.1.1         Design and trace finite state machines, pushdown automata, linear bounded automata, and Turing machines.
CSA 473.1.2         Describe and use non-deterministic automata.
CSA 473.1.3         Describe and use regular expressions.
CSA 473.1.4         Describe and determine the absolute and relative, computational capabilities of automata variants.
CSA 473.1.5         Apply standard conversion algorithms to process automata and grammars.
CSA 473.1.6         Read and create proofs establishing the equivalence or non-equivalence of automaton and/or grammars.
CSA 473.1.7         Design context-free grammars to describe a particular set of strings.
CSA 473.1.8         Demonstrate the difference between an ambiguous and unambiguous grammar and show that a grammar is ambiguous.
CSA 473.1.9         Show that a language is or is not in a given class of languages such as regular, context-free, non-regular.
CSA 473.1.10       Describe the closure properties of regular and context-free languages and be able to prove these closure properties.
CSA 473.1.11       Describe at least one algorithm for both top-down and bottom-up parsing.

CSA 473.2:     Describe the elements of the Chomsky hierarchy.
CSA 473.2.1:        Describe the power and limitations of automata and grammars.
CSA 473.2.2:        Describe the hierarchy of languages and grammars.
CSA 473.2.3:        Describe the Church's Thesis and its implications.
CSA 473.2.4:        Explain the fundamental decision procedures for regular languages.
CSA 473.2.5:        Prove that a language’s has a particular location in the Chomsky hierarchy.

CSA 473.3:     Explain how some problems have no algorithmic solution.
CSA 473.3.1:        Describe the basics of the theory of computation.
CSA 473.3.2:        Provide examples of problems that are undecidable and unrecognizable.
CSA 473.3.3:        Determine if a problem is decidable or recognizable.
CSA 473.3.4:        Be able to describe the nature of the Halting problem and prove that it is undecidable and recognizable.
CSA 473.3.5:        Demonstrate reducibility of one problem to another problem in proving that a problem is undecidable, recognizable, or decidable.

Required topics (approximate weeks allocated):

  • Introduction
    • mathematical preliminaries (1.0)
      • set theory
      • relations and functions
      • recursive definitions
      • mathematical induction
  • Context-free grammars and parsing
    • context-free grammars (1.5)
      • regular grammars
      • context-free grammars and languages
    • parsing (1.5)
      • left most derivations
      • top-down parsing
      • bottom-up parsing
      • shift-reduce parsing
    • normal forms (1.0)
  • Automata and Languages
    • finite automata (1.0)
      • deterministic finite automata
      • state diagrams
      • nondeterministic automata
      • removing nondeterminism
      • finite automata and regular sets
    • regular languages and sets (2.0)
      • regular grammars and finite automata
      • nonregular languages
      • pumping lemma
      • closure of regular languages
    • pushdown automata and context-free languages (1.0)
      • pumping lemma for context-free languages
      • closure properties of context-free languages
    • turing machines (2.0)
      • standard Turing machines
      • Turing machines as language acceptors
      • nondeterministic Turing machines
      • equivalence of Turing machine variants
    • the Chomsky hierarchy (1.0)
      • context-sensitive languages
      • linear bounded automata
  • Decidability (2.0)
    • decision problems
    • church-Turing hypothesis
    • the halting problem
    • universal Turing machine
    • reducibility
    • undecidable problems
  • Exams/Review (1.0)

Graduate students:

Students enrolled in CSA 573 will be given additional readings and/or assignments.