Compsci 334, Fall 2024, Exam 3

Exam 3 topics (from LinzRodger 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 Linz
  • Other models of TM
  • Universal TM
  • Enumeration procedure
  • Linear Bounded Automata

• Chapter 11 Linz
  • Recursively Enumerable Languages
  • Recursive Languages
  • Unrestricted Grammar
  • Context Sensitive Grammar

• Chapter 12.1 Linz
  • Decidability
  • The Halting Problem

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
• Chapter 11 - Unrestricted grammars

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.