Exam01 study topics
Exam01 will deal with math, and regular languages:
The following topics are fair game for exam01:
- 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).
- 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(Regexp1)=L(M1))
involves showing both
L(Regexp1) ⊆ L(M1) and
L(M1) ⊆ L(Regexp1).
The following will not be on the exam:
- regular grammars
- The proof of uncountability of real numbers
radford.edu