CPS 140, Spring 2012, Test 2 Review

TEST 2 topics

• General Knowledge of Chapters 1-5, 7 Linz

• 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)
  • Turing machines as building blocks handout!
  • Big-O analysis

• Parsing - Chap 8 JFLAP
  • First and Follow sets
  • building an LL(1) parse table
  • building an LR(1) parse table
  • LL(k) and LR(k)
  • comparison of LL(1) and LR(1) parser to brute-force parser

• L-Systems
  • Write an L-System
  • understand an L-System program

---

Ways to Study for the Exam

• Old tests (see link in index)
• homework problems
• problems in the book
• use JFLAP to check problems
• bake or buy cookies and make TMs, eat them when done!

---

TEST 2 Logistics

• Closed book, closed notes, closed neighbor
• Here are 5 types of problems on the exam:
  • write a TM (transition diagram or Building Blocks)
  • write an L-System or interpret an L-System program
  • Transform a CFG to another form
  • Build an LL and/or SLR Parse Table - all steps
  • pumping lemma proof
  • there are other problems too!

---