Automata
Homeworks for the
course CS 3350, Fall 2021
General comment. The main purpose of most homeworks is to
show how well you understand the algorithms.
In many cases, the resulting finite automata, pushdown automata,
and Turing machines can be simplified, but please first
literally apply the algorithm so that we know that you can use
it.
If in addition to this, you also show how to make the
corresponding Turing machine or finite automaton or whatever more
concise, nothing wrong with that, the TA may even give you some
extra points (if she has time to grade these additional things).
But the most important thing is to show that you can follow the
algorithm.
For simple examples that we give you as homeworks:
 you
may immediately see how to convert, e.g., a contextfree grammar
into a Chomsky normal form,
 but if someone gives you a more
complex case, you will have to use the algorithm.
So, it is
important to learn how to follow the algorithm.
If you deviate from the algorithm, how do we know that you learned
the algorithms? It was the same with sorting.
 Of course,
if someone gives you a list of 4 numbers on the test, you can sort
them yourself easily.
 The purpose of the question was that you
show that you understand mergesort, quicksort etc., not that
you sort 4 numbers.
In general:  If after you
show that you understand the algorithm you also provide a simpler
answer  great,
 but not instead of following the
algorithm.
1. (Due September 2) In class, we designed automata for
recognizing integers and real numbers.
1.1. Use the same ideas to describe an automaton for recognizing
names of classes in Java. In Java, this name should start with a
capital letter, and contain only letters, digits, or the underscore
symbol. To describe an automaton, draw a picture like we did in
class.
A natural idea is to have 3 states: start (s), correct class name
(c), and error (e). Start is the starting state, c is the only
final state. The transitions are as follows:
 from s, any
capital letter A, ..., Z lead to c, every other symbol leads to e;
 from c, any digit, any letter, and the underline symbol lead
back to c, every other symbol leads to e;
 from e, every symbol
leads back to e.
1.2. Trace, stepbystep, how this finite automaton will check
whether the following two words (sequences of symbols) are correct
names for Java classes:
 the word Java (which this
automaton should accept) and
 the word C++ (which this
automaton should reject).
1.3. Write down the tuple <Q, Σ, δ, q_{0},
F> corresponding to this automaton:
 Q is the set of all
the states,
 Σ is the alphabet, i.e., the set of all the
symbols that this automaton can encounter; for simplicity, consider
only four symbols: the plus sign, letters a and A, and an
underscore;
 δ: Q x Σ → Q is the function that
describes, for each state q and for each symbol s, the state
δ(q,s) to which the automaton that was originally in the
state q moves when it sees the symbol s (you do not need to
describe all possible transitions this way, just describe two of
them);
 q_{0} is the starting state, and
 F is the
set of all final states.
1.4. Apply the general algorithm for union and intersection to:
 this automaton as Automaton A, and
 a more realistic
version of an automaton for recognizing unsigned integers  that
automaton is described in the examples lecture  as Automaton B;
in the example described in the lecture, we assumed, for
simplicity, that, in addition to 0 and 1, only the symbol a is
allowed; in reality, any other symbol different from 0 and 1 
including symbols A and underscore  leads to the error state
e.
For simplicity, in your automaton for recognizing the union
and intersection of the two languages, feel free to assume that you
only have symbols 0, a, A, underscore, and +.
Solution to Homework 1
2. (Due September 2)
 Use the general algorithm
that we learned in class to design a nondeterministic finite
automaton that recognizes the language (+ U −)(0 U 1)*;
reminder:
 0 is a language consisting of only one 1symbol
word 0;
 AB means concatenation;
 transform the
resulting nondeterministic finite automaton into a deterministic
one.
Solution to Homework 2
3. (Due September 9) Apply the general algorithm for
transforming the finite automaton into a regular language (i.e., a
language described by a regular expression) to the following
automaton. This automaton has two states: s (= straightA student)
and e (= everyone else); s is the starting state, it is also the
final state. The only two symbols are A and B. From s, A leads back
to s, and B leads to e. From e, any symbol leads back to e.
Solution to Homework 3
4. (Due September 9) Prove that the following language is
not regular {a^{2n}b^{n}, n = 0, 1, 2, ...} =
{Λ, aab, aaaabb, aaaaaabbb, ...}.
Solution to Homework 4
5. (Due September 16) Write and test a method that emulates
a general finite automaton. The input to this method should
include:
 the number N of states; these states are
q_{0}, ..., q_{N − 1}; we assume that
q_{0} is the start state;
 the number M of symbols;
these states are 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. Turn in:
 a file containing
the code of the method,
 a file containing the code of the
program that you used to test this method, and
 a file
containing 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 16) Show, step by step, how the following
pushdown automaton will recognize a sequence ++−−. This
pushdown automaton has two states:
 the starting state A,
and
 the final state B.
The transitions are as follows:
 From A to A, the transition is +, ε, → +;
 From A to B, the transition is: −, + → ε;
 From B to B, the transition is −, + →
ε.
Solution to Homework 6
7. (Due September 16) Show, step by step, how the grammar
with rules S → ε and S → +S− will generate
the word ++−−.
Solution to Homework 7
8. (Due September 16) In a lecture, we described an
algorithm that, given a finite automaton, produces a contextfree
grammar  a grammar that generate a word if and only if this word
is accepted by the given automaton.
 On the example of the
automaton from Homework 3, show how this algorithm will generate
the corresponding contextfree grammar.
 On the example of a
word AAA 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.
Solution to Homework 8
9. (Due September 16) Use a general algorithm to construct a
(nondeterministic) pushdown automaton that corresponds to
contextfree grammar described in Problem 7. Show, step by step,
how the word ++−− will be accepted by this
automaton.
Solution to Homework 9
10. (Due October 7) Transform the grammar from Homework 7
into Chomsky normal form.
Solution to Homework 10
11. (Due October 7) Use the general algorithm to transform
the pushdown automaton from Problem 6 into a contextfree grammar.
Show, stepbystep, how the resulting grammar will generate the
word ++−−.
Solution to Homework 11
12. (Due October 7) Show, step by step, how the stackbased
algorithm will transform the expression (1 − 3) * (5 −
7) into a postfix expression, and then how a second stackbased
algorithm will compute the value of this postfix expression.
Solution to Homework 12
13. (Due October 14) 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 in the arithmetic expression are onedigit numbers,
i.e., each of these numbers is either 0, or 1, or 2, ..., or 9. For
example, your program should correctly process expressions like
2+3*4, but there is no need to process expressions like 11+22. For
simplicity, assume that the only arithmetic operations are addition
+, subtraction −, and multiplication *.
Comments:
 as with all programming assignments for
this class, submit a file containing the code, and a file
containing 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.
14. (Due October 21) For the LL(1) grammar that we studied
in class, with rules S → F, S → (S + F), and F → a,
show how the word ((a + a) + a) can be represented as uvxyz in
accordance with the pumping lemma for contextfree grammars. Show
that the corresponding word uvvxyyz will be generated by this
grammar.
Solution to Homework 14
15. (Due October 21) Prove that the language consisting of
all the words that have equal number of +'s and −'s and
exactly two times as many opening parentheses is not
contextfree.
Solution to Homework 15
16. (Due November 4) Design a Turing machine that, given a
positive unary number n, add 2 to this number. Test it,
stepbystep, on the example of n = 2.
Solution to Homework 16
17. (Due November 4) Design a Turing machine that, given a
positive binary number n greater than or equal to 8, subtracts 8
from this number. Test it, stepbystep, on the example of n =
9.
Solution to Homework 17
18. (Due November 4) Use the general algorithm to transform
a finite automaton from Homework 3 into a Turing machine. Show
stepbystep, on an example of a word AAA, how this word will be
recognized by your Turing machine.
Solution to Homework 18
19. (Due November 4) As we discussed in a lecture, 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 that computes n − 1 for a binary
number n = 4, 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.
Solution to Homework 19
20. (Due November 11) 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 head of the
Turing machine changes 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 head 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 head 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.
21. (Due November 11) Give two examples:
 an example
of computation time which makes an algorithm feasible according to
the formal definition but not practically feasible, and
 an
example of 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.
Solution to Homework 21
22. (Due November 11) 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?
Solution to Homework 22
23. (Due November 18) Prove that the cubic root of 5 is not
a rational number.
Solution to Homework 23