ÍÃ×ÓÏÈÉú

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:

CSE 274 and (MTH 231 or MTH 331)

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 CSE 573 will be given additional readings and/or assignments.

Learning Outcomes:

1. Design and trace automata and grammars
   • Design and trace finite state machines, pushdown automata, linear bounded automata, and Turing machines
   • Describe and use non-deterministic automata
   • Describe and use regular expressions
   • Describe and determine the absolute and relative computational capabilities of automata variants
   • Apply standard conversion algorithms to process automata and grammars
   • Read and create proofs establishing the equivalence or non-equivalence of automata and/or grammars
   • Design context-free grammars to describe a particular set of strings
   • Describe and prove the closure properties of regular and context-free languages
2. Describe the elements of the Chomsky hierarchy
   • Describe the power and limitations of automata and grammars
   • Describe the hierarchy of languages and grammars
   • Describe the Church-Turing Thesis and its implications
   • Prove that a language has a particular location in the Chomsky hierarchy
3. Explain how some problems have no algorithmic solution
   • Describe the basics of the theory of computation
   • Provide examples of problems that are undecidable and unrecognizable
   • Determine if a problem is decidable or recognizable
   • Describe the operation of a Universal Turing Machine
   • Describe the nature of the Halting problem and prove that it is undecidable and recognizable
   • Demonstrate reducibility of one problem to another problem in proving that a problem is undecidable, recognizable, or decidable
4. (Graduate students only) Describe oracle Turing machines and compare them with Turing machines
5. (Graduate students only) Review additional research literature and relate their findings to topics in the course