Compsci 334, Spring 2022, Exam 3

Exam 3 topics (from Linz book)

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

• Chapter 8 Linz
  • pumping lemma for CFL
  • properties of CFL

• Chapter 9 Linz
  • formal definition of Turing machine
  • write a Turing machine (transition diagram)
  • Big-O analysis

• Turing Machine Building Blocks (see notes)

• L-systems (see notes)

• Chapter 10.1-10.3 Linz
  • Other models of TM
  • Nondeterministic TM

Exam 3 topics (from JFLAP book)

• Chapter 7 - Transforming grammars
• Chapter 9 - Write and understand a multitape Turing machine
• Chapter 10 - Write and understand an L-System

Old Exams

There is a page of old exams and solutions

Here are some old questions that are specific to the topics we have done.

• Spring 2021 Exam 2, Questions
  • Question 7
• Spring 2021 Exam 3, Questions
  • Questions 2, 3 (b, d, e), 6-9
• Spring 2019 Exam 2, Questions
  • Questions 1, 2, 9-12
• Spring 2018 Exam 2, Questions
  • Questions 1, 2, 5, 9-12
• Spring 2014 Exam 2, Questions
  • Questions 1, 2, 3, 5, 9-12
• Spring 2012 Exam 2, Questions
  • Questions 1, 2, 8-11

Exam 3 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.