| Final Study Guide |
Final format:
- 140 points total (176 with xc)
- 8 written problems, 2 worth 10 points, 6 worth 20 points
- 2 additional extra credit written problems, worth 16 and 20 points
- An information sheet will be included with the final; other than
that, it is a closed-notes exam.
Final topics:
- Continuation passing style
- Know how to translate a program into CPS
- Lambda calculus
- know the difference between lazy and eager evaluation
- know how to evaluate to a normal form (one to which beta-reduction
does not apply)
- be able to recognize non-terminating expression
- Church encoding
- know how to encode Booleans in the lambda-calculus and write simple
functions over them
- know how to encode numbers in the lambda-calculus and write simple
functions over them
- Combinatory logic
- know how to translate lambda-calculus expressions to combinatory
logic
- Natural / transition semantics
- know how to write natural / transition semantics derivations for
expressions
- know the difference between natural / transition semantics
- given a rule, identify whether it is a transition / natural
semantics rule
- Context free grammars
- be able to prove that a grammar is ambiguous (using an example
string)
- be able to disambiguate a simple grammar (recall the MP on this
subject)
- DFA (a few points only)
- know which class of languages they recognize
- know which other common formalism recognizes this class.
- other common facts
|
|