Challenge Problems in Automata and Formal Languages
Revised October 30, 2005.
The purpose of these problems is to provide a challenge to the top students,
meaning those who master the regular material of the course and would like
to learn more.
Do not try to work these problem to improve a poor grade ... if you are doing
badly in the course, concentrate on the regular material.

Fix a constant n.
Let L_{1} be the the language over the alphabet {a,b} consisting
of all strings of the form uav where u and v are strings and u = n.
Let L_{2} be the the language over the alphabet {a,b} consisting
of all strings of the form uav where u and v are strings and v = n.

Give an NFA with n+2 states that accepts L_{1}.

Prove that no NFA with fewer than n+2 states can accept L_{1},
or find one with fewer states.

Give an NFA with n+2 states that accepts L_{2}.

Prove that no NFA with fewer than n+2 states can accept L_{2},
or find one with fewer states.

Give a DFA with n+2 states that accepts L_{1}.

Prove that the minimal DFA that accepts L_{2} has exactly
2^{n+1} states.

Some people say you "can't get" pi, that is, the wellknown ratio of
the circumference of a circle to its diameter. Are they right? What does
that even mean? Work these problems.

Prove that, if P = NP, RSA coding is insecure. (You must, of course,
first define "insecure.")
What is a publickey encryption system? Give a sensible, mathematically
rigorous, definition.
Is it true that, if P = NP, publickey encryption is impossible?

Let L_{halt} = {<M>w  M accepts w}.
We know that L_{halt} is undecidable, but if M is simple and
w is short, we would intuitively think that, if M eventually halts with input
w, it shouldn't take too many steps. However, this intuition is wrong.
Prove the following theorem:
If f is any
recursive function,
there is a number n and a string <M>w in L_{halt} of length
no more than n, such that M does not halt with input w in the first
f(n) steps.
Turing Machine Emulation
Detailed description of the CYK algorithm.