Computer Science 60
Principles of Computer Science
Spring 2009
Assignment 12: NPDAs and Uncomputability!
Due Sunday, April 26 at 11:59 PM
What to submit
Part 1 of this assignment is a JFLAP problem and the JFLAP file will
be submitted through the submission server. Please name your file NPDA.jff.
Part 2 comprises proofs and these should be submitted on paper in
class (either on April 27 or April 28, depending on which section
you're in).
Please be sure to staple your sheets of paper
together and put your name on each sheet.
Part 1: Nondeterministic Pushdown Automata [30 Points, Individual]
In class, we proved that the language of binary palindromes is not
regular but we also showed that it does have a context-free grammar.
In this problem, you will show that this language is context-free
using a different approach - namely by building a nondeterministic
pushdown automaton (NPDA) for it. Use JFLAP to construct a NPDA for
the language of all binary palindromes: strings of zero or more 0's
and 1's that are the same backwards as forwards. Please name your
file NFA.jff.
Part 2: Millisoft! [40 Points, Individual]
You have been hired by Millisoft, a large software company with
numerous famous
products that include Millisoft Sentence (word processing
software), Succeed (a spreadsheet program), Energydot (presentation
software), among others.
Your boss, Gill Bates, drops by your spacious cubicle sipping a
refreshing and stimulating
Jolt
Cola ("All the sugar, and twice the caffeine!").
Gill begins by reminding you that a decider is a program
that takes an input and eventually halts and accepts (says "yes" to
its inputs) or rejects (says "no" to its input). For example, a
decider for the prime numbers would take a number, perhaps encoded
in binary, as input and would eventually halt saying "yes" (it's prime) or
"no" (it's not prime).
- "OK, so here's your first task," says Gill. "We have decided to
change our interview process -- we're going to ask
all of our job candidates to see if they
can write a decider which takes as input a string of
0's and determines whether the number of 0's present is a power of 2.
Here's what I need from you," continues Gill.
"I need a program which we'll call a Power of Two Decider Tester
(POTDT). The POTDT takes as input a program.
The POTDT then decides whether P is a legitimate decider for strings whose
length is a power of 2. That is, the POTDT eventually halts and
says yes if the program it received was a correct
submission for this competition and otherwise the POTDT halts and
says no. I need this POTDT program written by tomorrow
at 6 AM."
Prove to Gill that this cannot be done, not by 6 AM
and not EVER! You may use diagrams to help explain your proof,
but your proof must be clear, precise, and rigorous. Your
submission on this and the following problem
will be graded on clarity and precision of explanation.
- "Drat!" says Gill upon hearing the news. "OK, then, in that case,
I'd like you to
write a program called a Regularity Checker (RC). The Regularity
Checker takes as input a program P (e.g., a Turing Machine) and it
needs to determine
whether or not the set of strings accepted by P is a
regular language. The RC must always halt with an answer of yes
or no!" Prove to Gill that this too is impossible. Again, you
may use pictures to help you explain your proof, but your proof
must be clear, precise, and rigorous.
Note that if a turing machine runs forever on an input, that input is
considered REJECTED for the purposes of defining the language
that the TM accepts. This might help!
Note: The idea in both of these problems is similar to the examples
we did in which we reached a contradiction by creating a
halt-checker out of the program that we hope to prove uncomputable. In this case, you'll
want to create a halt-checker from a POTDT and a RC. Keep in mind that you
can build any function/program/machine you like in order to coax the POTDT and
RC into deciding whether a program P halts on an input w.