CS3252: Theory of Automata - Professor Xenofon Koutsoukos

Completed Assignments

1
2
3
4
5
6
7
8
9
10
11

Reviewed Assignments (Final Exam)

8
- Silly proofs
- Ambiguity in grammars
- Designing PDAs
9
- Designing PDAs
- Tracing PDA execution
10
- Eliminating epsilon productions
- Eliminating unit productions
- Eliminating useless symbols
- Putting grammar into Chomsky Normal Form
11
- Following IDs of Turing machines
- Creating Turing machines

qrstuvwyz

Reviewed Assignments

1 (essay)
2
- Create DFA's
- Examine DFA's
3
- NFA to DFA conversion
  - Lazy eval
  - Describe its language
4
- Design NFA's
- Epsilon closure
- e-NFA to DFA conversion
5
- Convert DFA to regex by state elimination method
- Convert regex to e-NFA's
- Eliminate e-transitions from e-NFA's
- Proving equality of regexps
6
- Pumping lemma
7
- Minimum-state equivalent DFA

Lectures

1
- Logistics & goals
2
- Basic definitions
3
- Drawing transition diagrams / tables
4
- NFA
- Subset construction / lazy evaluation
5
- e-NFAs
6
- Intro to RE
7
- Convert RE to e-NFA
8
- Algebraic manipulation of RE
- Testing algebraic laws
9
- Pumping lemma
10
- Closure properties
- Homomorphisms???
11
- Runtime of representation conversions (DFA to NFA to etc)
12
- Equivalence & minimization

MOOC (Stanford lectures)

https://www.youtube.com/channel/UCHuRxy3-6SNP2mQt2MOoWiw/videos

Questions