Homeworks for the course CS 3350, Fall 2016

1. (Due August 30) Design an automaton that recognizes identifiers
in Java. Show, on two examples, how it works: an example of a
correct identifier and an example of a string which is not a
correct identifier. *Reminder:* a identifier in Java starts
with a letter and may have letters, digits, or underscore symbols
_ after that.

2. (Due August 30) Design an automaton that accepts only binary strings in which the number of 1s is equal to 1 modulo 3 (i.e., has 1, 4, 7, ... ones). For example, your automaton should accept a string 100 or a string 101110, but not a string 00111.

3. (Due August 30) 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 0s. This automaton has two states:

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

4. (Due September 6) 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, q2 and q3 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 September 6) 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 September 6) 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 September 6) Show, step-by-step, how to form a
non-deterministic automaton corresponding to the following regular
expression: 1(0^{*} U 1).

8. (Due September 13) Show, step-by-step, how the general algorithm will produce a regular expression that corresponds to automaton that accepts the language of all the binary sequences that have even number of 1s. A finite automaton for recognizing this language is similar to Automaton B from Problem 3, the only difference is that in the new automaton, the state b1 is final and the state b2 is not final.

9. (Due September 20, extra credit if turned in by September 13) 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 numbers 0, 1, 2, ..., s − 1;
- when s = 2, symbols are 0 and 1, so we consider general binary sequences;
- when s = 3, symbols are 0, 1, and 2;
- etc.

- 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 September 20) 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 September 20) Let L be a language of all expressions consisting of open and close square brackets and of letters b and c, in which the number of open square brackets [ is equal to the number of closed square brackets ]. For example, the strings [b] and c]]b[[c are in this language, but the string [[b] is not. Prove that this language is not regular.

12. (Due September 20) 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
00001111.

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

14. (Due October 4) Use the general algorithm to transform the following context-free grammar into a pushdown automaton: S --> 1T0, T --> 0S1, S --> ε, T --> ε. Show, step-by-step, how the word 1010, which is generated by the original context-free grammar as S --> 1T0 --> 10S10 --> 1010, will be accepted by the resulting pushdown automaton.

15. (Due October 11) The textbook has a 4-state pushdown automaton
from that recognizes the language {ww^{R}: w is in
{0,1}^{*}}; in my edition, it is Figure 2.19, it may have
a different number in other editions. Use the general algorithm to
transform this automaton into a context-free grammar. Show how the
word 0110, which is accepted by this automaton, will be generated
by this grammar.

16. (Due October 25 for extra credit, due November 1 for regular
credit) Use the pumping lemma for pushdown automata to prove that
the language {www: w is in {0,1}^{*}} is not context-free.
*Hint:* feel free to appropriately modify the book's proof
about the language {www: w is in {0,1}^{*}}.

17. (Due October 25) Step by step transform the following CFG to Chomsky normal form: S --> 1T0, T --> 0S1, S --> ε, T --> ε.

18. (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 stack-based algorithms that we recalled in class).

19. (Due November 8) Show, on the first few steps of a Turing
machine recognizing the language
{a^{n}b^{n}c^{n}, n = 0, 1, 2, ...}, how a
Turing machine can be represented as a finite automaton with two
stacks.

20. (Due November 8) Transform a finite automaton B from Problem 3 into a Turing machine. Show step-by-step, on an example of a word 101, how this word will be recognized by your Turing machine.

21. (Due November 22, for extra credit by November 15) Write a method that emulates a 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 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 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 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

- we have N = 7 states:
q
_{0}= start, q_{1}= inNumber, q_{2}= state1, q_{4}= state0, q_{5}= accept, and q_{6}= reject; - we have M = 3 symbols:
s
_{0}= _, s_{1}= 0, and s_{2}= 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 --> state1, R means that state[1][2] = 2, symbol[1][2] = 2, and lr[1][2] = R, etc.

22. (Due November 15)
Design a Turing machine for computing n − 2
in *unary* code; for n = 0 and for n = 1, it should return 0.
Trace it on two examples: n = 1 and n = 4.

23. (Due November 29, for extra credit due November 22) The disadvantage of representing a tape as an array -- as in Problem 21 -- 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 the symbol at the head's location and all the symbols after that, while
- the first stack represents all the symbols before the head.