Compsci 334, Spring 2022, Exam 2

Exam 2 topics (from Linz book and lecture notes)

• Chapter 4
  • Properties of regular languages
  • Pumping lemma
  • Proof by contradiction
  • Given L, is it regular?

• Chapter 5
  • write a CFG
  • parse trees
  • ambiguous grammar
  • brute force parser

• Chapter 7
  • write an NPDA or DPDA, formal definition, transition diagram
  • algorithm: CFG to NDPA
  • algorithm: NPDA to CFG

• Parsing
  • First and Follow sets
  • LL Parsing
  • SLR Parsing (also known as LR Parsing)

Exam 2 topics (from JFLAP book)

• Chapter 5 - Pushdown Automata
• Chapter 6 - Context-free grammars
• Chapter 8 - LL and SLR Parsing

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 old 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 2.

• Spring 2021 Exam 2 - Questions
  • Question 1-6, 8-10
• Spring 2019 Exam 1 - Questions
  • Questions 2, 3, 4, 7, 8
• Spring 2019 Exam 2 - Questions
  • Question 1 - should be able to recognize those that are REG and CFL
  • Question 2a, 2b, 2c
  • Questions 3, 4, 5, 6, 7, 8
• Spring 2018 Exam 1 - Questions
  • Question 2, 3, 4, 7, 8
• Spring 2018 Exam 2 - Questions
  • Question 1 - should be able to recognize those that are REG and CFL
  • Question 2 - a, c, d
  • Questions 4, 6, 7, 8
• Spring 2014 Exam 1 - Questions
  • Question 2, 3, 4, 5, 8, 9
• Spring 2014 Exam 2 - Questions
  • Question 1 - should be able to recognize those that are REG and CFL
  • Question 2 - b, e, f
  • Questions 4, 5, 6, 7, 8
• Spring 2012 Exam 1 - Questions
  • Question 2, 3, 4, 5, 8, 9
• Spring 2012 Exam 2 - Questions
  • Question 1 - should be able to recognize those that are REG and CFL
  • Question 2 - b, c, e
  • Questions 3, 4, 5, 6, 7

In general all Test 1 problems are good, ignore questions on Test 2's that involve pumping lemma, Turing machines, l-systems, properties with CFL, and transforming grammars to another form.

Exam 2 Logistics

• The exam is in person during class.
• Exam is closed notes and closed book. Bring a pen or pencil
• The exam is your own work, do not consult with anyone.