Automata, Computability, and Formal Languages
- you are allowed up to 5 pages of
- if you need extra pages, place your name
on each extra page;
- the main goal of most questions is to
show that you know the corresponding algorithms; so, if you are
running out of time, just follow the few first steps of the
1. Illustrate the pumping lemma for context-free grammars by
showing how it will represent the word w = +01 which is generated
by the CFG with starting variable S and rules S → N, S →
IN, I → +, I → −, N → DN, N → D, D
→ 0, and D → 1 as uvxyz. Show, step-by-step, how the
corresponding word uvvxyyz can be derived from this CFG.
2. Prove that the language of all the words that have an equal
number of a's and b's, and twice as many c's is not
3. Design a Turing machine that, given a
positive unary number n, adds 2 to this number. Test it,
step-by-step, on the example of n = 1.
4. As we
discussed in class, a Turing machine can be described as a finite
automata with two stacks:
- the right stack contains, on
top, the symbol to which the head points; below is the next symbol
to the right, then the next to next symbol to the right, etc.;
- the left stack contains, on top, the symbol directly to the
left of the head (if there is a one), under it is the next symbol
to the left, etc.
On the example a Turing machine from
Problem 3, show, step-by-step:
- how each state of the
corresponding Turing machine can be represented in terms of two
- how each transition from one state to another can
be implemented by push and pop operations.
5. Design a Turing machine that, given two unary numbers, computes
their sum. Test it, step-by-step, on the example of 1 + 2.
6. Give two examples:
- an example of an
computation time which makes an algorithm feasible according to
the formal definition but not practically feasible, and
example of a computation time for which the corresponding
algorithm is practically feasible, but not feasible according to
the formal definition.
These examples should be different
from what you learned in class -- a minor difference is OK.
7. Use the general algorithm to transform the following finite
automaton for recognizing possibly signed binary integers to a
Turing machine. This automaton has a starting state s, an
intermediate state i, a final state f, and a sink state k, and the
- from s, + or − lead to i,
while 0 or 1 lead to f;
- from i, 0 or 1 lead to f, while + or
− lead to sink;
- from f, 0 or 1 lead to f, while + or
− lead to sink.
Show, step-by-step, how your Turing
machine will accept the word +01.
8. Use the general algorithm to transform the following PDA into a
two-tape Turing machine. This PDA recognizes words of the type
, where w is any word, and wR
same word reversed.
For example, if w = ab, then wR = ba, and
wwR = abba.
The pushdown automaton has 4 states:
- the starting state
- the reading state r,
- the checking state c, and
the final state f.
The transitions are as follows:
From s to r, the transition is:
- From r to r, the transitions are:
r to c, we have a jump ε, ε → ε.
From c to c, the transitions are:
- From c to f, the only
Show, step-by-step, how the resulting Turing machine will
recognize the sequence abba
9. What is NP? What is P? What is NP-complete? What is NP-hard?
Give brief definitions. Give an example of an NP-complete problem.
Is P equal to NP?
10. Formulate Church-Turing thesis. Is it a mathematical theorem? Is
it a statement about the physical world?