Automata
Homeworks for
the course CS
3350, Fall 2017
General comment: Unless explicitly specified, each homework
should be turned in on a sheet of paper: draw an automaton like we did
in class and like the book does, do whatever else needed,
add your name on top and turn it in by the beginning of the class
on the day when the homework is due.
1. (Due September 6) A recommended name for a class in Java should
start with a capital letter, and have only letters (small or capital),
digits, and an underscore symbol _. Design an automaton that
recognizes such names, and check it on two examples:
 a recommended Java class name, and
 a sequence of symbols which is not a recommended Java class
name.
2. (Due September 6) Use the algorithm that we learned in class,
with pairs of states from two automata as states of the new
deterministic automaton, to design the automata recognizing the
union and the intersection of the languages A and B corresponding
to the following automata:
 The automaton corresponding
to the language A has three states:
 the starting state
a_{1},
 the final state a_{2}, and
 a sink
state a_{3}.
The transitions are as follows:
 From a_{1}, 1 leads us to a_{2}, any
other symbol (0, +, or −) leads to the sink.
 From
a_{2}, any symbol leads to the sink.
 The
automaton corresponding to the language B also has three states:
 the starting state b_{1},
 the final state
b_{2}, and
 a sink state b_{3}.
The
transitions are as follows:  From b_{1}, 0 or 1
leads us to b_{3}, any other symbol (+ or −) leads
to the b_{2}.
 From b_{2}, 0 or 1 lead us back to
b_{2}, any other symbol (+ or −) leads to the sink.
3. (Due September 13) Use the algorithm that we learned in class
to design a nondeterministic automaton recognizing the
language (a U b)^{*}(a U b):
 start with
nondeterministic automata recognizing a and b; for example, a
nondeterministic automaton recognizing a has two states, the
start state and the final state, and the only transition is that
when we are in the start state, a leads to the final state;

use the general algorithm for the union of languages represented
by nondeterministic automata to design a nondeterministic
automaton recognizing the language a U b;
 apply the general
algorithm for the Kleene star to your automaton recognizing a U b,
and come up with an automaton that recognizes the language (a U
b)^{*};
 apply the general algorithm for the
concatenation to your automata recognizing (a U
b)^{*} and a U b, and get an automaton recognizing the language (a U
b)^{*}(a U b).
4. (Due September 20) Use the general algorithm to transform the
nondeterministic automaton from Problem 3 into a deterministic one.
5. (Due September 20) Write a method that emulates a general finite
automaton. The input to this method should include:
 the
number N of states q_{0}, ..., q_{N − 1}; we
assume that q_{0} is the start state;
 the number M of symbols s_{0}, ... s_{M −
1};

an integer array state[n][m] that describes to what state the
finite automaton moves if it was in the state q_{n} and sees
the symbol s_{m};
 a boolean array final[n] that
tells us, for each state, whether this state is final or not.
This program needs to keep track of a current state.
Initially, this location is 0.
Your program should emulate the work of the finite automaton
stepbystep. Return the printout of the method, the printout of
the program that you used to test this method, and the printout of
the result of this testing. Feel free to use Java, C, C++,
Fortran, or any programming language in which the code is
understandable.
6. (Due September 27) Apply the general algorithm for transforming
the finite automaton into a regular language to Automaton B from
Problem 2.
7. (Due September 27) Automaton B from Problem 2 accepts the word
+010.
 Trace, stepbystep, that this word is indeed
accepted by the given automaton.
 Use this tracing to find the
parts x, y, and z of this word corresponding to the Pumping Lemma.
 Trace that the words xyyz and xyyyz are also accepted by this
automaton.
8. (Due October 4, due September 27 for extra credit) Prove that
the following language is not regular
{0^{n}1^{n}2^{n}} = {Λ, 012,
001122, 000111222, ...}.
9. (Due October 18) In class, we had a pushdown automaton for
recognizing words of the type ww^{R}, where w is any word,
and w^{R} means the same word reversed.
For example, if w = ab, then w^{R} = ba, and
ww^{R} = abba.
The automaton that we came up with has 4 states:
 the
starting state s,
 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: for every possible symbol a, b,
...
 From r to c, we have a jump ε, ε →
ε.
 From c to c, the transitions are: for
every possible symbol a, b, ...
 From c to f, the only
transition is:
Show, stepbystep, how this automaton will recognize the sequence
classssalc.
10. (Due October 18) The following contextfree grammar (CFG)
generates palindromes. This CFG has the following rules:

S → ε,
 S → a,
 S → b,
 ...,
 S → z,
 S → aSa,
 S → bSb,
 ...,
 S → zSz.
On an example of a palindrome abba, show,
stepbystep, how this palindrome will be generated by this
grammar.
11. (Due October 18) On the example of the Automaton B from
Problem 2, show how the general algorithm will produce a
contextfree grammar that generates all the words accepted by this
automaton  and only words generated by this automaton. On the
example of a word +010 accepted by this automaton, show how the
tracing of acceptance of this word by the finite automaton can be
translated into a generation of this same word by your
contextfree grammar.
12. (Due October 25, extra credit if turned in on October 18)
Apply, stepbystep, the general algorithm for transforming a
contextfree grammar into Chomsky normal form to the contextfree
grammar from Problem 10 (limit yourselves to only two letters a
and b).
13. (Due October 25) Use a general algorithm to construct a
(nondeterministic) pushdown automaton that corresponds to the
contextfree grammar from Problem 10.
14. (Due November 1) Apply, stepbystep, the general algorithm of
converting a pushdown automaton to a contextfree grammar to the
pushdown automaton from Problem 9. Explain how the acceptance of
the word abba by this automaton will be translated into a
derivation of this word in the resulting grammar.
15. (Due November 1) Show, step by step, how the stackbased
algorithm will transform the expression (1 − 2) * (3 −
4) into a postfix expression, and then how a second stackbased
algorithm will compute the value of this postfix expression.
16. (Due November 8) Write a program that, given an arithmetic
expression,
 first transforms it to a postfix form, and
then
 computes its value (by using the stackbased algorithms
that we recalled in class).
You can assume that all the
numbers are onedigit ones. Comments:  as with all
programming assignments for this class, submit a printout of the
code, and a printout of an example of what this program generates
on each step;
 ideally, use Java, but if you want to write it
in some other programming language, check with the TA that it is
OK; usually, C or C++ are OK.
17. (Due November 8) Illustrate the pumping lemma for contextfree
grammars by showing how it will represent the word s = acb which
is generated by the CFG with starting variable S and rules A
→ ε, S → AS, S → SB, A → a, B →
b, and S → c, as uvxyz. Show, stepbystep, how the
corresponding word uvvxyyz can be derived from this CFG.
18. (Due November 15) Prove that the language of all the words
that have equal number of a's, b's, and c's is not
contextfree.
19. (Due November 15) Design a Turing machine that, given a
positive unary number n, subtracts 1 from this number. Test it,
stepbystep, on some example.
20. (Due November 15) Design a Turing machine that, given a
positive binary number n, subtracts 1 from this number. Test it,
stepbystep, on some example.
21. (Due November 15) Transform a finite automaton B from Problem
2 into a Turing machine. Show stepbystep, on an example of a
word 010, how this word will be recognized by your Turing
machine.
22. (Due November 22) Write a method that emulates a general
Turing machine. The input to this method should include:

the number N of states q_{0}, ..., q_{N −
1}; we assume that q_{0} is the start state, that the
lastbutone state q_{N − 2} is the accept state,
and the last state q_{N − 1} is the reject state;
 the number M of symbols s_{0}, ... s_{M −
1}; we assume that s_{0} is the blank state _;

an integer array state[n][m] that describes to what state the
Turing machine moves if it was in the state q_{n} and sees
the symbol s_{m};
 an integer array symbol[n][m] that
describes what symbol should be on the tape after the Turing
Machine in the state q_{n} sees the symbol s_{m}
(it may be the same symbol as before, or it may be some other
symbol written by the Turing machine);
 a character array
lr[n][m] that describes, for each state q_{n} and for each
symbol s_{m}, whether the Turing machine moves to the left
(L), or to the right (R), or stays in place (blank symbol);

the integer array of a large size describing the original contents
of the tape, i.e., what symbols are written in each cell.
This program needs to keep track of a current location of the
head. Initially, this location is 0.
Your program should emulate the work of the Turing machine
stepbystep. Return the printout of the method, the printout of
the program that you used to test this method, and the printout of
the result of this testing. Feel free to use Java, C, C+++,
Fortran, or any programming language in which the code is
understandable.
Example: A Turing machine for checking whether a binary
string is even (i.e., ends with 0) has the following rules:
 start, _ > inNumber, R
 inNumber, 1 > state1, R

inNumber, _ > reject
 inNumber, 0 > state0, R
 state0,
1 > state1, R
 state0, 0 > state0, R
 state1, 1 >
state1, R
 state1, 0 > state0, R
 state1, _ > reject
 state0, _ > accept
In this case:  we have N =
6 states: q_{0} = start, q_{1} = inNumber,
q_{2} = state1, q_{3} = state0, q_{4} =
accept, and q_{5} = reject;
 we have M = 3 symbols:
s_{0} = _, s_{1} = 0, and s_{2} = 1;
Here:  The first rule start, _ > inNumber, R means that
state[0][0] = 1, symbol[0][0] = 0, and lr[0][0] = R.
 The
second rule inNumber, 1 > state1, R means that state[1][2] = 2,
symbol[1][2] = 2, and lr[1][2] = R, etc.
23. (Due November 22) Give two examples:
 an example of an
computation time which makes an algorithm feasible according to
the formal definition but not practically feasible, and
 an
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.
24. (Due November 22) What is NP? What is P? What is NPcomplete?
What is NPhard? Give brief definitions. Give an example of an
NPcomplete problem. Is P equal to NP?
25. (Due November 22, by November 15 for extra credit) 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 21, show, stepbystep:  how each state of the
corresponding Turing machine can be represented in terms of two
stacks, and
 how each transition from one state to another can
be implemented by push and pop operations.
26. (Due November 22) Apply the general algorithm for transforming
a PDA into a 2tape Turing machine to the PDA that recognizes words
of the type a^{n}b^{n}. Show, stepbystep, how your
Turing machine will accept the word aabb.