Automata,
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: 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 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.

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:

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.

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) = n2.

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 {0n1n} -- 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 {wwR} -- 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 {0n1n}-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 uv2xy2z can be derived from this CFG.

19. (Due date October 28) Use pumping lemma to prove that the language {anb2nc3n, 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 {anbn} to design a Turing machine for recognizing the language {anbncn}. 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 210, i.e., in binary code, 102, can be done as follows:

Example: to add 102 to the binary number 101102, 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 110002.

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

Trace it on an example.

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:

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

27. (Due November 25) 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:

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:

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.