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

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.

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:

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

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.

19. (Due November 8) Show, on the first few steps of a Turing machine recognizing the language {anbncn, 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:

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 checking whether a binary string is even (i.e., ends with 0) has the following rules:

In this case: Here:

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:

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