Compsci 334, Fall 2024, Exam 2

Exam 2 topics (from LinzRodger book and lecture notes)

• 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 15
  • Difference between Top-Down and Bottom-up Parsers
  • First and Follow sets

• Chapter 16
  • CFG to NPDA modelling LL Parsing
  • LL Parsing algorithm - how does it work
  • Build LL Parse table
  • LL(k)

• Chapter 17
  • CFG to NPDA modelling LR Parsing
  • SLR Parsing Algorithm - how does it work
  • Build LR parse table (includes building DFA)

Exam 2 topics (from JFLAP book)

• Chapter 5 - Pushdown Automata
• Chapter 6 - Context-free grammars
• Chapter 8 - LL and SLR Parsing

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