CS 254: Automata and Computability

Takehome exam. Due on paper 8:30AM Monday, 24 May 2010. Submit your program for problem #5 both on paper and via the Courses folder.

This is an open-notes, open-Internet, open-book exam. The only thing you aren't allowed to do is consult with other people about the exam (except for Jeff Ondich, with whom you may discuss the exam as much as you like).

  1. (8 points) Prove that every regular language is also a context-free language by describing a procedure for converting any DFA into an equivalent PDA. Then demonstrate your procedure by applying it to the DFA M1:

  2. (8 points) Prove that every regular language is also a context-free language by describing a procedure for converting an regular expression into an equivalent context-free grammar. Then demonstrate your procedure by applying it to the regular expression "(ab)*(a+b)"

  3. (8 points) Write a Turing Machine that accepts any string of 1's and 0's, but with a twist. Before the TM enters its accepting state, it should add 1 to the binary number represented by the string of 1's and 0's it is accepting. If the string on the tape when the TM starts running contains anything other than 1's and 0's and the left end marker X, the TM should enter the reject state (i.e. your TM should be total in the sense defined on p.213 of Kozen).

    To make this easier than it would otherwise be, you may assume that the binary string's least significant bit is at the start of the TM's tape. For example, a starting tape of "X 1 0 1 1 blank blank blank ..." would represent the (base ten) integer 13 rather than 11. (Why does this make things easier? Imagine what needs to happen when your string is "X 1 1 1".)

  4. (8 points) On page 195 of your textbook, Kozen describes techniques for proving closure properties for CFLs by combining their corresponding CFGs in clever ways. For this problem, you will do something similar by combining PDAs rather than CFGs.

    In particular, suppose A1 and A2 are the languages accepted by the PDAs P1 and P2, respectively. Prove that CFLs are closed under union by showing how to construct a PDA P that accepts A1 ∪ A2.

  5. (8 points) Consider the program expressions.py. This is a very small program illustrating how a simple grammar for infix arithmetic expressions can be turned quite directly into Python code that evaluates those expressions.

    Your job is to extend the code in this program to successfully parse and evaluate the arithmetic expressions described by:

    <expression> -> <term> | <term>+<expression>
    <term> -> <number> | <number>*<term>
    <number> -> 0|1|2|3|4|5|6|7|8|9

    where <expression> is the start symbol and <number> is a single-digit non-negative integer.

    For (3 points) extra credit, modify the grammar to include parentheses and multi-digit non-negative integers, and modify your program accordingly. If your program contains any loops, it won't count for extra points. If you submit an extra credit program, you must submit two versions of the of the program--one to cover the grammar shown above, and another covering your extended grammar (this requirement is to prevent your fancy extra credit code from damaging your fine code for the main problem).