Exam02 study topics
Exam02 will deal mostly with,
but may still include questions about DFAs/NFAs and regular expressions.
The following topics are fair game for exam02:
- Material covered by hw04, hw05:
PDAs, CFGs (rules with
→
vs. derivations using ⇒
), parse-trees, and TMs.
- Material already covered by hw01–hw03 and exam01.
The exam won't focus on these topics extensively,
but will still require understanding:
Math (incl. notations) for sets and common set operations,
our definition of language
,
concatenation of languages,
tuples,
functions and relations,
DFAs/NFAs (as tuples, knowing the types of each element and the standard letters we've used for them).
- 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).
- 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).
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).
- 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 .
radford.edu