Automata,
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: Reading the symbol 0 in each state leads to the same state, reading the symbol 1 in b1 leads to b2, and reading the symbol 1 in b2 leads to b1.

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.

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:

Store the set of accept states in a boolean array accept of size n, and the next states in a 2-D array next. Once the automaton is formed, your program should be able to check whether a given string of digits is accepted by this automaton.

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 {0n1n} -- 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,

You can assume that all the numbers are one-digit ones. Comment: as with other programming assignments, submit a printout of the code, and a printout of the example of what this program generates.

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 {a3nb2ncn, 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 {anbncn}. 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:

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

In this case: Here:

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:

Write down the first 5 values f(0), ..., f(4) of the function f(n) for the following case:

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:

Use a general algorithm for composition to design a new Turing machine that computes the function h(n) = f(g(n)). Trace, step-by-step, how the next Turing machine works for n = 0 and for n = 2.

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:

Modify your program for simulating the Turing machine by using this two-stacks representation of a tape.

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.