Compsci 334, Spring 2021, Exam 1

Rodger office hours for Wed 2/17 and Thur 2/18

• WED Feb 17 - Office hours shifted to 6pm-7pm
• Thur, Feb 18 - Office hours: 9:15am-9:45am

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 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

• Exam is open book and open notes.
• The exam is your own work, do not consult with anyone or use jflap or any other tool, or search for answers on the web.
• Take the exam on gradescope.
• You have one hour 40 minutes. You need to start anytime between 10:00am and 10:15am. You must start by 10:15am.
• Type in answers or upload a .pdf or image. You can draw a DFA on paper and then either scan it or take a picture of it and upload it.
• Here are some symbols and how to enter them.
  • If typing a grammar rule use -> (2 symbols, dash and greater than) for the arrow, such as S -> a
  • To type empty string use &
  • To type empty set use {}
  • When writing a regular expression type * , it does not have to be above. So a* + b is a starred or b