Automata
Homeworks for the course CS 3350, Fall 2017

General comment: Unless explicitly specified, each homework should be turned in on a sheet of paper: draw an automaton like we did in class and like the book does, do whatever else needed, add your name on top and turn it in by the beginning of the class on the day when the homework is due.

1. (Due September 6) A recommended name for a class in Java should start with a capital letter, and have only letters (small or capital), digits, and an underscore symbol _. Design an automaton that recognizes such names, and check it on two examples:

2. (Due September 6) Use the algorithm that we learned in class, with pairs of states from two automata as states of the new deterministic automaton, to design the automata recognizing the union and the intersection of the languages A and B corresponding to the following automata:

3. (Due September 13) Use the algorithm that we learned in class to design a non-deterministic automaton recognizing the language (a U b)*(a U b):

4. (Due September 20) Use the general algorithm to transform the non-deterministic automaton from Problem 3 into a deterministic one.

5. (Due September 20) Write a method that emulates a general finite automaton. The input to this method should include:

This program needs to keep track of a current state. Initially, this location is 0.

Your program should emulate the work of the finite automaton 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. Feel free to use Java, C, C++, Fortran, or any programming language in which the code is understandable.

6. (Due September 27) Apply the general algorithm for transforming the finite automaton into a regular language to Automaton B from Problem 2.

7. (Due September 27) Automaton B from Problem 2 accepts the word +010.

8. (Due October 4, due September 27 for extra credit) Prove that the following language is not regular {0n1n2n} = {Λ, 012, 001122, 000111222, ...}.

9. (Due October 18) In class, we had a pushdown automaton for recognizing words of the type wwR, where w is any word, and wR means the same word reversed.

For example, if w = ab, then wR = ba, and wwR = abba.

The automaton that we came up with has 4 states:

The transitions are as follows: Show, step-by-step, how this automaton will recognize the sequence classssalc.

10. (Due October 18) The following context-free grammar (CFG) generates palindromes. This CFG has the following rules:

On an example of a palindrome abba, show, step-by-step, how this palindrome will be generated by this grammar.

11. (Due October 18) On the example of the Automaton B from Problem 2, show how the general algorithm will produce a context-free grammar that generates all the words accepted by this automaton -- and only words generated by this automaton. On the example of a word +010 accepted by this automaton, show how the tracing of acceptance of this word by the finite automaton can be translated into a generation of this same word by your context-free grammar.

12. (Due October 25, extra credit if turned in on October 18) Apply, step-by-step, the general algorithm for transforming a context-free grammar into Chomsky normal form to the context-free grammar from Problem 10 (limit yourselves to only two letters a and b).

13. (Due October 25) Use a general algorithm to construct a (non-deterministic) pushdown automaton that corresponds to the context-free grammar from Problem 10.

14. (Due November 1) Apply, step-by-step, the general algorithm of converting a pushdown automaton to a context-free grammar to the pushdown automaton from Problem 9. Explain how the acceptance of the word abba by this automaton will be translated into a derivation of this word in the resulting grammar.

15. (Due November 1) Show, step by step, how the stack-based algorithm will transform the expression (1 − 2) * (3 − 4) into a postfix expression, and then how a second stack-based algorithm will compute the value of this postfix expression.

16. (Due November 8) Write a program that, given an arithmetic expression,

You can assume that all the numbers are one-digit ones. Comments:

17. (Due November 8) Illustrate the pumping lemma for context-free grammars by showing how it will represent the word s = acb which is generated by the CFG with starting variable S and rules A → ε, S → AS, S → SB, A → a, B → b, and S → c, as uvxyz. Show, step-by-step, how the corresponding word uvvxyyz can be derived from this CFG.

18. (Due November 15) Prove that the language of all the words that have equal number of a's, b's, and c's is not context-free.

19. (Due November 15) Design a Turing machine that, given a positive unary number n, subtracts 1 from this number. Test it, step-by-step, on some example.

20. (Due November 15) Design a Turing machine that, given a positive binary number n, subtracts 1 from this number. Test it, step-by-step, on some example.

21. (Due November 15) Transform a finite automaton B from Problem 2 into a Turing machine. Show step-by-step, on an example of a word 010, how this word will be recognized by your Turing machine.

22. (Due November 22) Write a method that emulates a general 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. Feel free to use Java, C, C+++, Fortran, or any programming language in which the code is understandable.

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:

23. (Due November 22) Give two examples:

These examples should be different from what you learned in class -- a minor difference is OK.

24. (Due November 22) What is NP? What is P? What is NP-complete? What is NP-hard? Give brief definitions. Give an example of an NP-complete problem. Is P equal to NP?

25. (Due November 22, by November 15 for extra credit) As we discussed in class, a Turing machine can be described as a finite automata with two stacks:

On the example a Turing machine from Problem 21, show, step-by-step:

26. (Due November 22) Apply the general algorithm for transforming a PDA into a 2-tape Turing machine to the PDA that recognizes words of the type anbn. Show, step-by-step, how your Turing machine will accept the word aabb.