Compsci 334, Spring 2022, Exam 1

Exam 1 topics (from Linz book)

• Chapter 1
  • proof by induction
  • set theory
  • languages

• Chapter 2
  • write a DFA or NFA, formal definition, transition diagram
  • Algorithm: NFA to DFA
  • Algorithm: DFA to Minimal DFA
  • Prove that an operation applied to a regular language results in a regular language.

• Chapter 3
  • write a regular expression (re)
  • write a regular grammar (rg), formal definition
  • algorithm: re to nfa
  • algorithm: dfa to re
  • algorithm: rg to dfa
  • algorithm: dfa to rg

Exam 1 topics (from JFLAP book)

• Chapter 1-4

Old Exams

There is a page of old exams and solutions, but be aware that we are having three exams and all the previous semesters they had 2 exams. That means some of the first exams will have topics we have not covered.

Here is a list of a few of the old exams and topics relevant to your Exam 1.

• Spring 2021 Exam 1 - All Questions
• Spring 2019 Exam 1 - Questions
  • Question 1
  • Question 2c, 2d, 2e, 2g
  • Question 5
  • Question 6 (the figure at the top of page 3 goes with this question
  • Question 9
• Spring 2018 Exam 1 - Questions
  • Question 1
  • Question 2a, 2b, 2g,
  • Question 5
  • Question 6 (the figure at the top of page 3 goes with this question
  • Question 9
• Spring 2014 Exam 1 - Questions
  • Question 1
  • Question 2a-2e
  • Question 6
  • Question 7 (the figure at the top of page 3 goes with this question
  • Question 10
• Spring 2012 Exam 1 - Questions
  • Question 1
  • Question 2a, 2f, 2g
  • Question 6
  • Question 7 (the figure at the top of page 3 goes with this question
  • Question 10
• Spring 2011 Exam 1 - Questions
  • Question 1
  • Question 2b-2e
  • Question 3
  • Question 6
  • Question 7 (the figure at the top of page 3 goes with this question
  • Question 10

In general ignore questions that involve CFG, NPDA, pumping lemma, and parse trees.

Exam 1 Logistics

• The exam is in person in our regular scheduled classroom at 5:15pm on Tuesday, Feb. 1.
• Exam is closed book and closed notes.
• The exam is your own work, do not consult with anyone.