Goals and Learning Objectives
Goals
- Study various automata, such as deterministic and nondeterministic finite-state machines, pushdown
automata, and Turing machines.
- Study formal languages of different kinds, such as regular and context-free languages.
- Understand the connections between languages and automata, and related algorithms for
transformations.
- Understand the basic results on computability, including undecidable problems such as the halting and
Post correspondence problems, and their significance.
- Study the basics of intractability, including NP-completeness and related topics.
- Make connections between theoretical results and topics in practical software development, such as
finite automata and regular-expression libraries.
- Improve programming skills, with emphasis on connections between theoretical results and practical
software.
Student Learning Outcomes
Students should be able to
- determine the detailed action of given automata on given inputs (e.g., determine whether a given DFA
accepts a given string).
- devise simple automata to satisfy given properties (e.g., devise a pushdown automaton to recognize a
given language).
- perform tasks analogous to the above for grammars and other linguistic formalisms (e.g., devising a
formal grammar for a language described in English).
- use standard algorithms to transform automata and languages in various ways (e.g., mapping
context-free grammars to pushdown automata).
- map instances of problems using standard reductions (e.g., 3-SAT to CLIQUE).
- demonstrate understanding of the above by writing suitable programs.