Compsci 334, Spring 2023, 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)

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

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.