Homeworks for the course

CS 3350, Spring 2016

1. (Due January 27) 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 January 27) Design an automaton that accepts only binary strings in which the number of 0s is divisible by 3. For example, your automaton should accept a string 100011, but not a string 00111.

3. (Due January 27) 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 even number of 1s. This automaton has two states:

- a starting state b1 (which is also final) and
- a state b2.

4. (Due February 1) Use a general algorithm that we learned in class to create a deterministic finite automaton from the following non-deterministic one: we have three states q1, q2, and q3; q1 is the starting state, q1 and q2 are final states.

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

5. (Due February 1) For the automata A and B described in Problem 3, use the general algorithm to produce a non-deterministic finite automaton corresponding to concatenation. Then use the genera; algorithm for transforming this non-deterministic finite automaton into a deterministic one.

6. (Due February 1) For the automaton B as described in Problem 3,
use the general algorithm to produce a non-deterministic finite
automaton corresponding to the Kleene star B^{*}.

7. (Due February 1) Show, step-by-step, how to form a
non-deterministic automaton corresponding to the following regular
expression: 0(1^{*} U 0).

8. (Due February 8) Show, step-by-step, how the general algorithm will produce a regular expression that corresponds to automaton B from Problem 3.

9. (Due February 15) Write a program that simulates 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.

10. (Due February 15) On an example of an automaton B described in Problem 3, for the word s = 10100, show how to get a decomposition s = xyz described in the Pumping Lemma.

11. (Due February 15) Let L be a language of all expressions consisting of open and close parentheses and of 0s and 1s, in which the number of open curly brackets { is equal to the number of closed curly brackets }. For example, the strings {0} and 1}}0{{1 are in this language, but the string {{0} is not. Prove that this language is not regular.

12. (Due February 15) Describe, step-by-step, how a pushdown
automaton for recognizing the language
{0^{n}1^{n}} -- which is described in the textbook
and which we also described in class -- recognizes a sequence
000111.

13. (Due February 22) Use the general algorithm that we learned in class to transform finite automaton A described in Problem 3 into a context-free grammar. Show, step-by-step, how this grammar will generate the word 0111 (which is accepted by the original automaton).

14. (Due February 22) Use the general algorithm to transform the following context-free grammar into a pushdown automaton: S --> 0T1, T --> 0S1, S --> ε, T --> ε. Show, step-by-step, how the word 0011, which is generated by the original context-free grammar as S --> 0T1 --> 00S11 --> 0011, will be accepted by the resulting pushdown automaton.

15. (Due March 2) Copy the correct solution to Problem 5 from the test - as posted on the class website - by hand, in your own handwriting. If you got 10/10 on this problem, you do not need to copy the proof, just turn in a sheet of paper with your name on it and a statement that you got 10/10 on this problem on the test.

16. (Due March 16) Use the general algorithm to transform the
following context-free grammar into Chomsky normal form:

S → B

S → bBaB

B → A

A → ε

17. (Due March 21) 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).

18. (Due March 28; extra credit if turned in by March 23) Illustrate the pumping lemma for context-free grammars by showing how it will represent the word s = bbbbaaaa, which is generated by the CFG with rules S --> bBa, B --> bSa, S --> e, as uvxyz. Show, step-by-step, how the corresponding word uvvxyyz can be derived from this CFG.

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

20. (Due April 6, extra credit if turned in by April 4) Use a general algorithm that we had in class to design a Turing machine that accepts exactly the words accepted by Automaton B from Problem 3. Illustrate, step-by-step, how it works, on the example of the word 011.

21.(Due April 6, extra credit if turned in by April 4)
Design a Turing machine for
recognizing the language
{a^{n}b^{n}c^{n}}. This machine should start
with the a-section, mark a word a, then go into b-section,
mark one of the b-symbols, etc.
Illustrate,
step-by-step, how it works, on two example: a word aabbcc that
belongs to this language, and a word aabc that doesn't belong to
the language.

22. (Due April 6, extra credit if turned in by April 4)
Design a Turing machine for computing n − 1
in *unary* code; for n = 0, it should return 0.
Trace it on two examples: n = 2 and n = 0.

23. (Due April 13) 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] = _.

24. (Due April 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) = n; - 1 is not a valid numerical code of a program;
- j
_{2}(n) = n − 1 for n > 0; j_{2}(0) = 0; - j
_{3}(n) = n − 5 for n = 5, 6, ...; for inputs n smaller than 5, the function j_{3}(n) does not halt; - j
_{4}(n) = n * n.

25. (Due April 25) Design a Turing machine that adds 2 to a binary number. Trace it step-by-step on the example of n = 2. Show, step-by-step, how the state of the Turing machine can be represented as a finite automaton with two stacks; explain what pop-push operations are needed to go from each state to the next one.

26. (Due April 27) Describe the rules of two Turing machines:

- the first Turing machine computes the function f(n) = n + 1 in unary code;
- the second Turing machine computes the function g(n) = n − 1 in unary code; for n = 0, take g(n) = 0.

27. (Due April 27) The disadvantage of representing a tape as an array -- as in Problem 23 -- 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.