CPS 140, Spring 2012, Test 1
TEST 1 topics
- Chapter 1
- proof by induction
- set theory
- Chapter 2
- write a DFA or NFA, formal definition, transition diagram
- Algorithm: NFA to DFA
- Algorithm: DFA to Minimal DFA
- Prove that an operation applied to a regular language results in a
regular language.
- Chapter 3
- write a regular expression (re)
- write a regular grammar (rg), formal definition
- algorithm: re to nfa
- algorithm: dfa to re
- algorithm: rg to dfa
- algorithm: dfa to rg
- Chapter 4
- Properties of regular languages
- Pumping lemma
- 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
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 DFAs, eat them when done!
TEST 1 Logistics
- Closed book, closed notes, closed neighbor
- Here are 4 types of problems on the exam:
- write a DFA for L
- write a CFG for L
- write an NPDA for L
- Prove that an operation applied to a regular language results in a
regular language.
- there are other problems too!
Office Hours between now and exam
- Prof Rodger - LSRC D237 -
Thursday Feb 16, 2:10-3:30pm
Monday, Feb 20, 2pm-4:15pm