Compsci 334, Spring 2021, Exam 2

Exam 2 topics (from Linz book)

• 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

• Chapter 6 Linz
  • removing lambda rules
  • removing unit productions
  • removing useless productions
  • transforming to CNF
  • GNF

Exam 2 topics (from JFLAP book)

• Chapter 5 - Pushdown Automata
• Chapter 6 - Context-free grammars
• Chapter 7 - Transforming 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 2019 Exam 1 - Questions
  • Question 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 - a, 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, g
  • 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, and properties with CFL.

Exam 2 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 an NPDA 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