Theory of Computation

Exam review

Regular Expressions Exam, Spring 2019

Sample exam - exam1_practice.txt

First exam

• exam1.docx
• exam1-solutions.docx
• Video solutions
  • Note - these videos play in the browser on some browsers (e.g., Chrome) and are downloaded by default on others (e.g., Safari)
  • DFA question 1a
  • Pumping Lemma question 1b
  • DFA question 1c
  • Pumping Lemma question 1d
  • Python3 regular expressions question 2
  • Proof by contradiction question 3a
  • Proof by induction question 3b
  • Contrapositive question 3c
  • DFA transition table question 4
  • What is the language question 5
  • Intersection of regular languages question 6

Context Free Languages Exam, Spring 2019

Sample exam - exam2_practice.txt Sample exam solutions - exam2_practice_solutions.docx

Final Exam, Spring 2019

Note that the initial sample exam did have some mistakes. Those mistakes were noted and fixed in the sample exam solutions document. Below is a video of me typing up and explaining my solution for each of the problems. In Firefox and Chrome these links play in the browser.

• sample exam
• sample exam solutions
• CFL language I.1
• DFA language I.2
• P language I.3
• NP language I.4
• Decidable language I.5
• Undecidable language I.6
• Python3 RE II.1
• RE Regular language properties II.2
• CFG III.1
• PDA III.2
• TM Configurations IV.1
• TM decidability IV.2