Compsci 334, Spring 2021, Exam 3

Exam 3 topics (from Linz book)

• 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

• 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 9 - Write and understand a multitape Turing machine
• Chapter 10 - Write and understand an L-System

Exam 3 topics (other, from lecture notes 4/22)

• Compilers - Different stages
• Comparison of Compilers vs Interpretors

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.

Most of the questions from the Exam 2's are relevant. Ignore topics we have already covered such as write a CFG, build an NPDA, etc.

One topic we DID NOT cover is Turing Machine with Building Blocks. Ignore those problems.

Exam 3 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 a Turing machine 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