Exam study topics
The exam will cover all topics that were covered on all homeworks (hw01-hw05).
In particular:
- Math (incl. notations) for sets and common set operations,
- our definition of
language
,
- concatenation of languages,
- tuples,
- functions and relations,
- Understanding the
contents of the
entire course in 45min
initial lecture,
including the table at the bottom, and being able to fill it in from scratch (including row- and column-titles).
- DFAs/NFAs (as tuples, knowing the types of each element and the standard letters we've used for them).
- DFAs, NFAs, converting from NFA to DFA, and regular expressions.
- Material covered by hw01–hw03.
- Understanding the structure of proofs:
when proofs need two directions: e.g.
showing that some grammar G1 and some machine M1
both generate/accept the same strings (that is, that L(G1)=L(M1))
involves showing both
L(G1) ⊆ L(M1) and
L(M1) ⊆ L(G1).
- PDAs (as tuples, knowing the types of each element and the standard letters we've used for them).
- CFGs (rules with
→
vs. derivations using ⇒
; parse-trees; ambiguity
- TMs — both deterministic and non-deterministic (as tuples, knowing the types of each element and the standard letters we've used for them).
- TMs — writing deterministic TMs
You will also need to be familiar with the following, from lectures but not explicitly on homeworks we had:
- The fact that strings can be enumerated (and hence TMs can be numbered).
- The fact that the reals in [0,1] are uncountable (non-enumerable) so by the pigeon-hole principle, there are numbers whose digits can't be streamed by any TM!
- How we encoded TMs as strings (in Ch17c notes).
- Universal Turing Machines: What language it accepts (but not the details of constructing it).
- The definition Decidable and Semidecidable languages.
- The definition of the Halting problem, the fact that it is undecidable, and the gist of how we showed that.
- Being able to state the Church-Turing thesis:
Any reasonable model of computation is equivalent to a TM (incl. Java, assembly,
and mentioned-only-in-passing models like
unrestricted grammars,
abacus machines,
the lambda calculus (a.k.a.
nothing but functions
)).
- The definitions of P, and of NP
(both definitions: as non-deterministic machine, as a deterministic verifier, and motivate why they're equivalent).
The definitions of NP-complete, and of a polynomial-time reduction.
The following will not be on the exam:
- regular grammars
- The proof of uncountability of real numbers
- Needing to read or write multi-tape or multi-track TMs,
nor the details of proving them equivalent to ordinary TMs.
I'd still hope you could describe to somebody how .
- The details of Cook's Th'm (that SAT is NP-complete).
radford.edu