CS 254: Automata and Computability
Takehome exam. Submit your answers electronically to
jondich@carleton.edu
by 5:00PM Monday, 6 June 2011.
This is an open-notes, open-Internet, open-book exam, with two restrictions:
(1) you may not consult with people other than Jeff Ondich about the exam,
and (2) if you encounter solutions to Kozen's problems anywhere, you need to
avert your eyes and ignore them.
I will be leaving town Sunday, June 5, and returning Friday, June 10. Since my
grades have to be submitted by 8:30 in the morning on June 8, it's essential that
you submit your test electronically, even if it's just via a scan of hand-written
solutions. Code for problem #2 should go to the Courses hand-in folder,
and everything else should come via e-mail.
- (10 points) Consider exercise #108 on page 343 of Kozen. Pick
exactly two of the four problems in this exercise, one decidable and one undecidable,
and provide proofs that your choices are correct. (If you want to do part (c), you might
find it useful to read problem #2 on page 309 for some thoughts about linear bounded automata.)
(10 points) This exercise involves experiments with
bison and
flex. If you have questions about C++,
please ask me for help. This exercise does not require much C++ knowledge (just some
output statements and obvious extensions of the C++ code you will see in the
sample code), but still, let me know if you run into trouble.
Note: I have made small adjustments to the calculator.y and calculator.lex files
to eliminate some unnecessary (and unused) code that was in one of the on-line
examples I used to build this exercise. I made these changes at noon on June 1, 2011.
You can get the old files at bison-old.
Submit your modified calculator.y and calculator.lex via the Courses hand-in folder. Submit
your answers to part (g) with the rest of your test.
If you need documentation for bison and flex, check out the
official
Bison manual or
this nice intro
to Bison from the University of Utah.
- Make a directory called "bison" and save
calculator.y,
main.cpp,
calculator.lex,
and calculator.h,
Makefile,
and expression.txt
in it.
- Open a Terminal window and cd to your bison directory.
- Look at calculator.y, main.c, calculator.lex, Makefile, and expression.txt.
- Build the program by executing the "make" command.
- Run the program by executing "calculator < expression.txt". Alternatively,
you can run calculator, type your expression on the next line, and then type Ctrl-D
alone on the line after that to terminate the input.
- Take another look at calculator.y, and make sure you understand which
context-free grammar it is parsing.
- If I give the calculator the input "2*3+4*5*6+7", in what order are the grammar
productions in calculator.y applied? Explain why this order makes sense.
To determine the order of production application, you can
insert print statements (e.g. cout << "Hello from rule 1" << endl;)
into calculator.y's rule actions. Your explanation might refer to a derivation
or a parse tree for the expression, and should definitely include a discussion of
how bison's parser generator handles operator precedence.
- Modify the grammar in calculator.y and the tokenizer in
calculator.lex to handle division and subtraction
with proper precedence behavior, as well as parentheses.
- (3 points extra credit) Modify the rule code in calculator.y to print out a parse tree
for the expression rather than a final value. This is tricky, and you may need to poke
around in the bison documentation.
- (2 points) What interesting thing in the computing world should I read
about this summer?
- (5 points) In class on May 27, Dave Diehl talked about making DFA's faster
to improve an intrusion prevention system. One way to make a DFA faster
is to reduce its number of states without changing the set of strings it recognizes.
Using the techniques described in chapters 13 and 14 of your textbook, do
problem 52(b) on page 328.