Homeworks for the course

CS 3350, Fall 2015

1. (Due September 2) Design an automaton that recognizes
floating-point real numbers in Java. Show, on two example, how it
works: an example of a real number and an example of a string which
is not a real number. *Reminder:* a floating point-real number
in Java is a fixed-point real number followed by the letter "e"
(small or capital) and an integer; examples: 1.5e3 or −.7e+2.

2. (Due September 2) Design an automaton that accepts only binary strings in which the number of 1s is divisible by 4. For example, your automaton should accept a string 11011, but not a string 00111.

3. (Due September 9) Use a general algorithm that we learned in class to design automata that accept the union and intersection of the following regular languages A and B. The language A is the language of all unsigned binary numbers, as represented by the following finite automaton:

0,1 <---- | | 0,1 | | -->a1-----> a2---->In this automaton A, only a2 is a final state. The language B is the language of all binary sequences that have odd number of 1s. This automaton has two states:

- a starting non-final state b1 and
- a final state b2.

4. (Due September 9) Use a general algorithm to create a deterministic finite automaton corresponding to the following non-deterministic one: we have three states q1, q2, and q3, q1 is the staring state, q2 is the only final state.

- From q1, reading 0 or 1 can lead to q2 or to q3.
- From q2, a jump can lead to q3, and from q3, a jump can lead to q2.

5. (Due September 16) For the automaton A as described in Problem 3,
use the general algorithm to produce a non-deterministic finite
automaton corresponding to the Kleene star A^{*}. Then use
the general algorithm for transforming this non-deterministic finite
automaton into a deterministic one.

6. (Due September 16) Use a general algorithm to describe a regular expression corresponding to the automaton A from Problem 3.

7. (Due September 23) Write a program that would simulate a finite automaton based on the user's specification. Your program should ask for:

- the number n of states; the states will be q
_{1}, q_{2}, ..., q_{n}; the state q_{1}is the starting state; - ask the user to indicate, one by one, whether each of the states
q
_{i}(1 ≤ i ≤ n) is an accept (final) state; - ask the user for the number s of symbols; symbols will be 0, 1, 2, ..., s − 1;
- for each state and each symbol, ask the user for the number of the next state.

*How to submit a program:* submit printouts of the code and
of the test results. Be prepared to show how the program works if
needed.

8. (Due date September 23) Prove that the square root of 15 is irrational.

9. (Due date September 23) Prove, by induction, that 1 + 3 + 5 + ... +
(2n − 1) = n^{2}.

10. (Due date September 30) On an example of an automaton described in Problem 3, for any sufficiently long sequence of symbols s accepted by this automaton, show how to get a decomposition s = xyz described in the Pumping Lemma.

11. (Due date September 30) Let L be a language of all expressions consisting of open and close parentheses, in which the number of open parentheses is equal to the number of closed parentheses. For example, the strings () and ))(( are in this language, but the string (() is not. Prove that this language is not regular.

12. (Due date October 7) Describe, step-by-step, how a pushdown automaton
for recognizing the language {0^{n}1^{n}} -- which is
described in the textbook -- recognizes a sequence 00001111.

13. (Due date October 7) Describe, step-by-step, how a pushdown automaton
for recognizing the language {ww^{R}} -- which is
described in the textbook -- recognizes a sequence 010010.

14. (Due date October 7) Transform a finite automaton A from Problem 3 into a context-free grammar.

15. (Due date October 14) Use a general algorithm to transform the
following grammar to Chomsky normal form:

S --> A

S --> aAbA

A --> B

B --> ε

16. (Due date October 21) Use a general algorithm to construct a pushdown automaton that recognizes the grammar described in Problem 15.

17. (Due date October 21) Use a general algorithm to construct a
context-free grammar corresponding to the
{0^{n}1^{n}}-recognizing pushdown automaton described in the
textbook.

18. (Due date October 28) Illustrate the pumping lemma by showing
how it will represent the word s = aaaabbbb, which is generated by
the CFG with rules S --> aAb, A --> aSb, S --> ε, as
uvxyz. Show, step-by-step, how the corresponding word
uv^{2}xy^{2}z can be derived from this CFG.

19. (Due date October 28) Use pumping lemma to prove that the
language {a^{n}b^{2n}c^{3n}, n = 0, 1,
...} is not context-free.

20. (Due date November 4) Write a program that, given 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). You can assume that all the numbers are one-digit ones. Submit a printout of the code, and a printout of the example of what this program generates.

21. (Due date November 4) Use a general algorithm that we had in class to design a Turing machine that accepts exactly the words accepted by Automaton A from Problem 3. Illustrate, step-by-step, how it works, on the example of the word 00.

22. (Due date November 4) Use the main ideas behind the Turing
machine that we had in class for recognizing the language
{a^{n}b^{n}} to design a Turing machine for
recognizing the language
{a^{n}b^{n}c^{n}}. Illustrate,
step-by-step, how it works, on two example: a word aabbcc that
belongs to this language, and a word aaba that doesn't belong to
the language.

23. (Due November 11) Design a Turing machine for computing n + 2
in *unary* code. Trace it on an example.

24. (Due November 11) Design a Turing machine for computing n + 2
in *binary* code. Assume that in the beginning, the binary
number is placed on the tape starting with its lowest bit. Trace
it on an example.

*Hint*: adding 2_{10}, i.e., in binary code,
10_{2}, can be done as follows:

- we ignore the lowest bit, and move one step to the right;
- then we follow
the same procedure as when we add 1 in binary code:
- we change all 1s to 0s and keep going right, until we see either a 0 or a blank;
- once we encounter a 0 or a blank, we replace it with 1;
- after that, we move back to rewind the tape.

*Example:* to add 10_{2} to the binary number
10110_{2}, which is stored on the tape as 01101, we ignore
0, and do the replacing. As a result, on the tape, we will have a
sequence 00011, which represents the binary number
11000_{2}.

25. (Due November 11) Design a 3-tape Turing machine for adding two binary numbers:

- the first two tapes contain the two inputs a and b;
- the result a + b should be placed on the third tape.

26. (Due November 11) In the proof that halting problem is not algorithmically solvable, we used a "diagonal" function f(n) which was defined as follows:

- f(n) = j
_{n}(n) + 1 is n is a valid numerical code of a (Java) program and j_{n}halts on n; - f(n) = 0 otherwise.

- j
_{0}(n) = 1; - 1 is not a valid numerical code of a program;
- j
_{2}(0) = j_{2}(1) = 0; for inputs n larger than 1, the function j_{2}(n) does not halt; - j
_{3}(n) = n − 5; - j
_{4}(n) = n * (n − 1).

27. (Due November 25) Write a method that emulates a Turing machine for computing. The input to this method should include:

- the number N of states q
_{0}, ..., q_{N − 1}; we assume that q_{0}is a start state, and that the last state q_{N − 1}is a halt 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 written on the tape if the Turing
Machine in the state q
_{n}sees the symbol s_{m}; - 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.

Your program should emulate 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.

*Example:* A Turing machine for adding 1 to a number in unary
code has the following rules:

- start, _ --> inNumber, R
- inNumber, 1 --> R
- inNumber, _ --> back, 1, L
- back, 1 --> L
- back, 0 --> halt

- we have
N = 4 states: q
_{0}= start, q_{1}= inNumber, q_{2}= back, and q_{4}= halt; - we have M = 2
symbols: s
_{0}= _ and s_{1}= 1.

- 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 --> R means that state[1][1] = 1, symbol[1][1] = 1, and lr[1][1] = R.
- The rule inNumber, _ --> back, 1, L means that state[1][0] = 2, symbol[1][0] = 1, and lr[1][0] = _.
- The rule back, 1 --> L means that state[2][1] = 2, symbol[2][1] = 1, and lr[2][1] = L.
- Finally, the rule back, _ --> halt means that state[2][0] = 3, symbol[2][0] = 0, and lr[2][0] = _.

28. (Due December 2) The disadvantage of representing a tape as an array -- as in Problem 27 -- is that we have a prior limit on the number of symbols that we need to emulate. A better way to simulate a Turing machine, as we mentioned in class, is to represent the contents of the type as a pair of stacks:

- the first stack represents all the symbols before the head, while
- the second stack represents the symbol at the head's location and all the symbols after that.

*Example*: Let us show how the Turing machine that adds 1 in
unary code is represented as two stacks. We will illustrate it on
the example of adding 1 to number 2, i.e., in the unary code, to
number 11. We will indicate the location of the head by placing
the letter H before and after the symbol at which the head is.

- In the beginning, the head is at the initial blank cell,
so the contents of the tape is H_H11. In this case:
- the first stack is empty, and the second stack has _11, with blank _ on top.

- Then, we move one step to the right,
the contents of the tape is _H1H1. In this case:
- the first stack has a blank _, and
- the second stack has 11.

- We move again, now the contents of the tape
is _1H1H, so:
- the first stack has 1_, with 1 on top, and
- the second stack has 1.

- We move once more, now on
tape we have _11H_H, so:
- the first tape has 11_, and
- the second tape has _.

- We replace blank with 1,
and move left. Now, on tape, we have _1H1H1, so:
- the first stack has 1_, and
- the second stack has 11.

- We move
to the left again, we have on tape _H1H11, so:
- the first stack has _, and
- the second stack has 111.

- We move
once again, now on tape we have H_H111, so:
- the first stack is empty, and
- the second stack has 111.