COM S 331
Offered during Fall and Spring Semesters each year.
- Credits and contact hours: 3 credits, 4 contact hours
- Instructor’s or course coordinator’s name: Gianfranco Ciardo
- Text book, title, author, and year: Introduction to the Theory of Computation, Michael Sipser.
- Other supplemental materials: Notes for ComS 331 Theory of Computing (instructor notes, 76 pages)
Specific course information
- Brief description of the content of the course: Models of computation: finite state automata, pushdown automata and Turing machines. Study of grammars and their relation to automata. Limits of digital computation, unsolvability and Church-Turing thesis. Relations between classes of languages.
- Prerequisites or co-requisites: Minimum of C- in Com S 228, MATH 166, and in COM S 230 or CPR E 310; ENGL 250
- Required, elective, or selected elective? Required
Specific goals for the course
- Specific outcomes of instruction: By the end of the course students should have a working knowledge (ability to solve problems with rigorously justified reasoning) of the following:
- Specifying formal languages using regular expressions, automata, or grammars. (6)
- Manipulating language representations: e.g., building the automaton equivalent to a grammar, minimizing a deterministic finite automaton, eliminating nondeterminism in a Turing machine). (1)
- Recognizing the power and limitations of regular, context-free, recursive, and recursively-enumerable languages.
- Understanding the halting problem and its implications to computer science.
- Understanding the power of nondeterminism.
- Using the pumping lemma to prove that a language is not regular/context-free.
- Using reduction to prove that a language is not recursive/recursively-enumerable.
Brief list of topics to be covered
- The concepts of formal languages as sets of strings over an alphabet, of grammar as language generators, and of automata as language acceptors.
- Finite automata, and their relation to regular expressions and regular grammars.
- Eliminating nondeterminism in finite automata, minimizing deterministic finite automata.
- The pumping lemma for regular languages.
- Closure properties for regular languages.
- Context-free grammars, and their relation to pushdown automata.
- Derivations, parse trees, and ambiguity for context-free languages.
- The pumping lemma for context-free languages.
- The importance on nondeterminism in pushdown automata.
- Closure properties for context-free languages.
- Turing machines and computational universality.
- The Church-Turing thesis.
- Decidable vs. semi-decidable languages, solvable vs. semi-solvable problems.
- Using reduction to prove that a language is not decidable.