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