Jkinne: 1 revision imported

2025-08-17T13:22:12Z

1 revision imported

← Older revision		Revision as of 13:22, 17 August 2025
(No difference)

wiki_previous>Znoble1: /* Standard Content */

2021-05-18T12:52:01Z

Standard Content

New page

== 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

CS 420 Theory of Computing - Revision history

Jkinne: 1 revision imported

wiki_previous>Znoble1: /* Standard Content */