Difference between revisions of "Theory of Computation"

From Computer Science
Jump to: navigation, search
(Regular Expressions Exam, Spring 2019)
(Final Exam, Spring 2019)
 
(12 intermediate revisions by the same user not shown)
Line 2: Line 2:
  
 
==Regular Expressions Exam, Spring 2019==
 
==Regular Expressions Exam, Spring 2019==
Sample exam was - [http://cs.indstate.edu/~jkinne/cs420-s2019/code/exam1_practice.txt]
+
Sample exam - [http://cs.indstate.edu/~jkinne/cs420-s2019/code/exam1_practice.txt exam1_practice.txt]
Final exam was - [http://cs.indstate.edu/~jkinne/cs420-s2019/code/exam1.docx]
+
 
Solutions to the final exam
+
First exam
*
+
* [http://cs.indstate.edu/~jkinne/cs420-s2019/code/exam1.docx exam1.docx]
 +
* [http://cs.indstate.edu/~jkinne/cs420-s2019/code/exam1-solutions.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)
 +
** [http://cs.indstate.edu/~jkinne/.video/exam1-1a-dfa.webm DFA question 1a]
 +
** [http://cs.indstate.edu/~jkinne/.video/exam1-1b-pumping-lemma.webm Pumping Lemma question 1b]
 +
** [http://cs.indstate.edu/~jkinne/.video/exam1-1c-dfa.webm DFA question 1c]
 +
** [http://cs.indstate.edu/~jkinne/.video/exam1-1d-pumping-lemma.webm Pumping Lemma question 1d]
 +
** [http://cs.indstate.edu/~jkinne/.video/exam1-2-python3-re.webm Python3 regular expressions question 2]
 +
** [http://cs.indstate.edu/~jkinne/.video/exam1-3a-contradiction.webm Proof by contradiction question 3a]
 +
** [http://cs.indstate.edu/~jkinne/.video/exam1-3b-induction.webm Proof by induction question 3b]
 +
** [http://cs.indstate.edu/~jkinne/.video/exam1-3c-contrapositive.webm Contrapositive question 3c]
 +
** [http://cs.indstate.edu/~jkinne/.video/exam1-4-transition-table.webm DFA transition table question 4]
 +
** [http://cs.indstate.edu/~jkinne/.video/exam1-5-explain-L.webm What is the language question 5]
 +
** [http://cs.indstate.edu/~jkinne/.video/exam1-6-reg-intersection.webm Intersection of regular languages question 6]
 +
 
 +
==Context Free Languages Exam, Spring 2019==
 +
Sample exam - [http://cs.indstate.edu/~jkinne/cs420-s2019/code/exam2_practice.txt exam2_practice.txt]
 +
Sample exam solutions - [http://cs.indstate.edu/~jkinne/cs420-s2019/code/exam2_practice_solutions.docx 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.
 +
* [http://cs.indstate.edu/~jkinne/cs420-s2019/code/exam3_sample/exam3_sample.txt sample exam]
 +
* [http://cs.indstate.edu/~jkinne/cs420-s2019/code/exam3_sample/exam3_sample_solutions.docx sample exam solutions]
 +
* [http://cs.indstate.edu/~jkinne/.video/exam3_sample_cf_I1.webm CFL language I.1]
 +
* [http://cs.indstate.edu/~jkinne/.video/exam3_sample_dfa_I.2.webm DFA language I.2]
 +
* [http://cs.indstate.edu/~jkinne/.video/exam3_sample_p_I3.webm P language I.3]
 +
* [http://cs.indstate.edu/~jkinne/.video/exam3_sample_np_I4.webm NP language I.4]
 +
* [http://cs.indstate.edu/~jkinne/.video/exam3_sample_decidable_I5.webm Decidable language I.5]
 +
* [http://cs.indstate.edu/~jkinne/.video/exam3_sample_undecidable_I6.webm Undecidable language I.6]
 +
* [http://cs.indstate.edu/~jkinne/.video/exam3_sample_python3_re_II1.webm Python3 RE II.1]
 +
* [http://cs.indstate.edu/~jkinne/.video/exam3_sample_reg_properties_II2.webm RE Regular language properties II.2]
 +
* [http://cs.indstate.edu/~jkinne/.video/exam3_sample_cfg_properties_III1.webm CFG III.1]
 +
* [http://cs.indstate.edu/~jkinne/.video/exam3_sample_pda_III2.webm PDA III.2]
 +
* [http://cs.indstate.edu/~jkinne/.video/exam3_sample_TM_config_IV1.webm TM Configurations IV.1]
 +
* [http://cs.indstate.edu/~jkinne/.video/exam3_sample_TM_problem_IV2.webm TM decidability IV.2]

Latest revision as of 19:35, 7 May 2019

Exam review

Regular Expressions Exam, Spring 2019

Sample exam - exam1_practice.txt

First exam

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.