CS 3723  Programming Languages  Spring 2014
Final Exam     Topics and Review

Exam date/time: Tuesday, 6 May 2014, 9:45 am - 12:15 pm. (2.5 hours)

1.1 Finite Automata
1.2 Regular Expressions
1.3 Subset Algorithm
1.4 Rec 8: DFAs & NFAs, Rec8.ans
1.5 Subset Algorithm with ε-moves
1.6 Rec 9. REs, ε-moves, Rec9.ans
1.7 RE−−>NFA

Types of Questions:

1. Given the diagram for an NFA (no ε-moves) use the subset algorithm to construct an equivalent DFA (accepts the same language).
2. Given the diagram for an NFA with ε-moves, determine the ε-closure of a set of states.
3. Given the diagram for an NFA with ε-moves, convert it to a DFA that accepts the same language. [Just have to take the ε-closure at each stage.]
4. Given the regular expression  a(ab|cd)  give an NFA (with or without ε-moves) that accepts the language described by the original regular expression.
   
5. Same question for  (a|b)cc
   
6. Same question for  (ac)*  [Hint: in 1.7 above, look up the way to add a * to any regular expression, and obtain the corresponding NFA with ε-moves.]

2.0 Python: Main Page
2.1 Regular Expressions in Python:
2.2 Rec 7: Python REs, Rec7.ans
2.3 Randomization and Python's Random Number Generator.

Types of Questions:

1. I give you a Python program that makes use of regular expressions and does something. I might ask you to explain the program, or alter it or add to it.
   
2. I give you a Python program that uses Python's random number generator to do something and ask questions about it, or ask you to alter it or add to it.

3.1 Rec 10: Lisp Functions, Rec10.ans
3.2 Lisp Lists
3.3 Rec 11: Lisp Lists, Rec11.ans

Types of Questions:

1. Write a recursive Lisp program to find an arithmetic result, such as the sum of a sequence, etc.
   
2. Write a recursive Lisp program to do something with one or more Lisp lists.
3. Give the result of evaluating a simple Lisp expression that involves lists, such as one of those in the middle link above. For example
   (list '(a (b c) d) '((e) f ((g))))   or
   (append '(a (b c) d) '((e) f ((g))))   or
   (apply '+ '(3 4 5)) 

4.0 Postscript: Main Page
4.1 Variables & Procedures
4.2 Example of Overlapping Boxes (first part)
4.3 Right Justifying Text (also centering)
4.4 Graphics

Types of Questions:

1. Given a specific string, give Postscript code to print it centered (horizontally and vertically) on an 8.5-by-ll inch page. (Vertical centering doesn't have to be exact.)
   
2. Given Postscript code that produces a simple figure at the origin, add code that will produce the same figure in the center of a page, rotated 90 degrees (positive angles go counterclockwise), and twice as big.
3. Give Postscript code that will print 20 circles centered at the origin with radii 5, 10, 20, ..., 50. You must use a Postscript for loop for this. [If I ask such a question, I will give you the Postscript commands to draw a circle, and the form of a Postscript  for  loop.]
4. As in problem 2 above, move this figure to the center of the page and increase its height by a factor of 2 and its width by a factor of 4.
5. I give you some code that draws lines, and you say what is drawn.