# Difference between revisions of "CS 420 Theory of Computing"

(Created page with "== Catalog Description == A sampling of the different areas of theoretical computer science: finite state concepts, formal grammars and automata, computability, Turing machine...") |
(→Standard Content) |
||

Line 6: | Line 6: | ||

== Standard Content == | == Standard Content == | ||

+ | ===Course Outline=== | ||

+ | |||

* closely follows the first 5 Chapters of the course textbook (see below), except that some topics are not covered in class | * closely follows the first 5 Chapters of the course textbook (see below), except that some topics are not covered in class | ||

* Regular languages: | * Regular languages: |

## Latest revision as of 12:52, 18 May 2021

## Contents

## Catalog Description

A sampling of the different areas of theoretical computer science: finite state concepts, formal grammars and automata, computability, Turing machines, and program verification. Prerequisite - C or better in CS 202 and CS 303.

## Prerequisites

Willingness to work hard. Knowing how to write a formal mathematical proof.

## Standard Content

### Course Outline

- closely follows the first 5 Chapters of the course textbook (see below), except that some topics are not covered in class
- Regular languages:
- Finite automata (DFA):
- Formal definition of finite automata, examples
- Formal definition of computation, designing finite automata
- Regular operators
- Nondeterminism:
- Formal definition of a nondeterministic finite automaton (NFA)
- Equivalence of NFAs and DFAs (with proofs)
- Closure under regular operations (with proofs)
- Regular expressions:
- Formal definition of a regular expression
- Equivalence with finite automata (with proofs)
- Nonregular languages
- The pumping lemma for regular languages (with proofs, students are expected to master how to use this lemma that certain languages are nonregular)
- Context-free languages:
- Context-free grammars (CFG)
- Formal definition of CFGs, examples of CFGs
- Chomsky normal form
- Pushdown automata (PDA)
- Formal definition of PDA, examples
- Equivalence of PDAs with CFGs, proof not covered in class
- Non-context-free languages:
- Pumping lemma for CFGs (students are expected to master how to use this lemma that certain languages are not context-free)
- Church-Turing thesis:
- Turing machines: formal definition, examples
- Variants of Turing machines, nondeterministic Turing machines, enumerators
- Definition of an algorithm
- Decidable languages:
- Decidable languages concerning regular languages, context-free languages
- Undecidability:
- Diagonalization method, examples of undecidable and Turing-unrecognizable languages
- Reducibility:
- Some undecidable problems, reduction via computation histories
- Computable function, mapping reducibility

### Learning Outcomes

- Basic understanding of fundamental computational models such as DFAs, NFAs, Turing machines, etc. and their properties.

### Important Assignments and/or Exam Questions

- Give a formal deﬁnition of a ﬁnite automaton.
- Let Bn = {ak | k is a multiple of n}. Show that for each n ≥ 1, the language Bn is regular.
- Use the pumping lemma to show that the language {0n1n0n1n} is not context free.
- Let Σ = {1,2,3,4} and C = {w ∈ Σ* | in w, the number of 1s equals the number of 2s and the number of 3s equals the number of 4s}. Show that C is not context-free.
- Deﬁne the following terms: (a) Turing-recognizable language, (b) co-Turing-recognizable language, (c) decidable language, (d) enumerator, (e) linear bounded automaton.
- What does it mean that language A is mapping reducible to language B?
- Let Q = {<M1,M2> | M1 and M2 are TMs and L(M1) = L(M2)}. Give a proof that Q is undecidable. You are allowed to use results from class.

### Standard resources

- Introduction to the Theory of Computation, 3rd Edition, by Michael Sipser. ISBN 978-1133187790