CS 254: Automata and Computability

Assignment #5

Due on paper by 8:30AM Wednesday, May 19.

This assignment is essentially a programming assignment. For each problem, you are trying to write a program in a programming language (PDAs in #1, and Turing machines in #2) to achieve a computational goal (acceptance of a particular set).

1. Create a push-down automaton that accepts the set of palindromes over {a,b}*. Your write-up should specify Q, Σ, Γ, the start state, the acceptance criterion (empty stack or final state), F (if you use final state acceptance), and δ. We can talk on Monday about ways of laying out δ on paper.
2. Create a Turing machine that accepts the set {ww | w ∈ {a, b}*}. As with problem #1, you'll need to specify all the compenents, including the transition rules, for your Turing machine.