Description
The Problems
10 points
1. At the very beginning of our discussion of chapter 4, we talked about framing computational
problems as languages. Here’s your chance to do just that. Suppose you want to show that a
DFA and a regular expression are equivalent. Express this problem as a language and show
that it is decidable. The constructions associated with Theorem 1.54 and the result from
Theorem 4.5 are relevant. To show that a language is decidable, you first need to express the
language formally then you need to show that there is a Turing machine that decides it. Use
Sipser’s notation for your Turing machine. Do not reducibility to solve this problem. That is a
matter for chapter 5.
10 points
2. Suppose S is the set of all infinite sequences of 0s and 1s. 001010101… is a member of S,
for example. Show that S is uncountable.
20 points
3. Let T = { 0
n1
n
| n >= 0 } , a set that we have considered many times. You’ll find the state
diagram for a PDA that recognizes T on p. 115. Call that PDA, P. Write a python program that
simulates P The program is invoked from the Linux command line.
The program must have a function that accepts a formal definition of P (p. 113) as a tuple
(Q, Σ, Γ, 𝛅, q0
, F) along with its input, w. This could either be a simple function, called, say,
“simulate,” or the constructor for a class called, say, “PDA.” The PDA will accept continuous
input, halting when the user types CTRL-c. It prints ‘accept’ for each string that is an element of
T, ‘reject’ if it is not. The PDA also rejects if a symbol is not an element of sigma or if a state is
not an element of Q.
2
The PDA is an extension of the DFA you wrote for Project 7. This time, instead of delta being a
simple function from a state and symbol to a new state, it is a function from a state, a symbol,
and stack top to a new state and new stack top.
Because you have to manipulate a stack as well as input, the PDA does not lend itself quite so
easily to the use of a dictionary. An approach, since the delta transitions are functions, is to
define functions for each of the states. If you choose this approach, rather than the dictionary
approach, you can relax the formal definition of the delta function.
