Homeworks for the course CS 3350, Spring 2022

*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 context-free grammar into a Chomsky normal form,
- but if someone gives you a more complex case, you will have to use 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.

- 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 January 27)** 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 constants in Java. In Java, this name should start with a letter and consist of all caps; digits and the underscore symbol are also allowed. To describe an automaton, draw a picture like we did in class.

A natural idea is to have 3 states: start (s), correct constant 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 capital letter, digit, or the underscore symbol lead back to c, every other symbol leads to e;
- from e, every symbol leads back to e.

1.2. Trace, step-by-step, how the finite automaton from Part 1.1 will check whether the following two words (sequences of symbols) are correct names for Java constants:

- the word PI2 (which this automaton should accept) and
- the word Pi2 (which this automaton should reject).

1.3. Write down the tuple <Q, Σ, δ, q_{0},
F> corresponding to the automaton from Part 1.1:

- 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 the 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 of two
automata *A* and *B* to:

- the automaton from
Part 1.1 as Automaton
*A*, and - an automaton for
recognizing unsigned binary integers -- with which we started this
class and which is described in the corresponding 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.

2. **(Due January 27)**

- Use the general algorithm that
we learned in class to design a non-deterministic finite automaton
that recognizes the language (A U B)(a U b)*; reminder:
- A, B, a, and b are languages consisting of only one 1-symbol word each: A is a language consisting of a single 1-symbol word A; a is a language consisting of a single 1-symbol word a, etc.;
- for any two languages C and D, the notation CD means concatenation;

- transform the resulting non-deterministic finite automaton into a deterministic one.

3. **(Due February 3)** 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: g (good student) and p
(student on probation); g is the starting state, it is also the
final state. The only three symbols are A, B, and F. From g, A and
B lead back to g, and F leads to p. From p, any symbol leads back
to p.

4. **(Due February 3)** Prove that the following language is not
regular {b^{n}a^{n+2}, n = 0, 1, 2, ...} = {aa,
baaa, bbaaaa, bbbaaaaa, ...}.

5. **(Due February 10)** Write and test a method that simulates
a general finite automaton. Your program should enable the computer
to simulate any given finite automaton and then to simulate, for
any given word, step-by-step, how this automaton decides whether
this word is accepted by the automaton.

The input to this method should include the full description of the corresponding finite automaton:

- the number N of states;
these states are q
_{0}, ..., q_{N − 1}; we assume that q_{0}is the start state; for simplicity, we describe the states by the corresponding integers 0, ..., N; - the number M of symbols; these symbols are s
_{0}, ... s_{M − 1}; for simplicity, we describe the symbols by the corresponding integers 0, ..., M; - an integer array
state[n][m] whose elements describe to what state the finite
automaton moves if it was in the state q
_{n}and sees the symbol s_{m}; and - a boolean array final[n] whose
elements describe, for each state q
_{n}, whether this state is final or not.

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.

6. **(Due February 10)** Show, step by step, how the following
pushdown automaton -- that checks whether a student has exactly as
many As than Bs -- will recognize a sequence ABAB. This pushdown
automaton has four states:

- the starting state s,
- the state "a" meaning that the number of As is larger than or equal to the number of Bs,
- the state "b" meaning that the number of Bs is larger than or equal to the number of As, and
- the final state f.

- From s to a, the transition is ε, ε → ε
- From a to a, the transitions are: A, ε → A; B, A → ε.
- From a to b, the transition is: B, ε → B.
- From b to b, the transitions are: B, ε → B; A, B → ε.
- From b to a, the transition is: A, ε → A.
- From a to f, the transitions are: ε, ε → ε.
- From b to f, the transitions are: ε, ε → ε.

7. **(Due February 10)** Show, step by step, how the grammar
with rules S → ε, S → ABS; S → ASB; S →
SAB; S → BAS; S → BSA; S → SBA; and S → SS;
will generate the word ABAB.

8. **(Due February 10)** In a lecture, we described an algorithm
that, given a finite automaton, produces a context-free 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 context-free grammar.
- On the example of a word ABB 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 context-free grammar.

9. **(Due February 10)** Use a general algorithm to construct a
(non-deterministic) pushdown automaton that corresponds to
context-free grammar described in Problem 7. Show, step by step,
how the word ABAB will be accepted by this automaton.

10. **(Due February 17)** Transform the grammar from Homework 7
into Chomsky normal form.

11. **(Due March 3)** Use the general algorithm to transform the
pushdown automaton from Problem 6 into a context-free grammar.
Show, step-by-step, how the resulting grammar will generate the
word ABAB.

12. **(Due March 3)** Show, step by step, how the stack-based
algorithm will transform the expression (3 − 1) * (5 −
8) into a postfix expression, and then how a second stack-based
algorithm will compute the value of this postfix expression.

13. **(Due March 10)** Write a program that, given an arithmetic
expression,

- first transforms it to a postfix form, and then
- computes its value (by using the stack-based algorithms that we recalled in class).

*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 March 24)** 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) + a) can be represented as uvxyz
in accordance with the pumping lemma for context-free grammars.
Show that the corresponding word uvvxyyz will be generated by this
grammar.

15. **(Due March 24)** Prove that the language consisting of all
the words in the alphabet {A, B, C} that have twice as many Bs as
Cs and three times as many As than Cs is not context-free.

16. **(Due April 7)** Design a Turing machine that, given a
positive unary number n, add 3 to this number. Test it,
step-by-step, on the example of n = 1.

17. **(Due April 7)** Design a Turing machine that, given a
positive binary number n greater than or equal to 16, subtracts 16
from this number. Test it, step-by-step, on the example of n =
18.

18. **(Due April 7)** Use the general algorithm to transform a
finite automaton from Homework 3 into a Turing machine. Show
step-by-step, on an example of a word ABF, how this word will be
processed by your Turing machine.

19. **(Due April 7)** 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.

- 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.

20. **(Due April 14)** Write and test a method that simulates a
general Turing machine. Your program should enable the computer to
simulate any given Turing machine for accepting-rejecting and then
to simulate, for any given word, step-by-step, how this Turing
machine decides whether this word is accepted or not.

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 last-but-one 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.

Your program should simulate the work of the Turing machine step-by-step. 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 April 14)** 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.

22. **(Due April 14)** 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?

23. **(Due April 21)** Prove that the cubic root of 6 is not a
rational number.