Automata
Homeworks for the course CS 3350, Spring 2020

General comments:

1. (Due January 22) In class, we studied an automaton for recognizing signed or unsigned binary integers. This automaton is easy to modify so that it will recognize all integers. The resulting automaton has 4 states: start (st), sign (si), integer (i), and error (e). Start is the starting state, integer is the only final state. The transitions are as follows:

Trace, step-by-step, how this finite automaton will check whether the following two words (sequences of symbols) represent syntactically correct integers: Write down the tuple <Q, Σ, δ, q0, F> corresponding to this automaton: Apply the general algorithm for union to automata recognizing signed and unsigned integers.

2. (Due January 30)

3. (Due February 6) Write and test 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.

4. (Due February 6) Apply the general algorithm for transforming the finite automaton into a regular language (i.e., a language described by a regular expression) to the following automaton. This automaton has two states: a and b, a is the starting state and both a and b are final states. The only two symbols are 0 and 1. From a, 0 leads to a, and 1 to b. From b, both 0 and 1 lead to a.

5. (Due February 13) Prove that the following language is not regular {a2nbn} = {Λ, aab, aaaabb, aaaaaabbb, ...}. Together with your proof, also provide the detailed proof that we had in class: that the language {0n1n, n = 0, 1, 2, ...} = {Λ, 01, 0011, ...} is not regular.

6. (Due February 13) Show, step by step, how the following pushdown automaton will recognize a sequence 000111. This pushdown automaton has two states:

The transitions are as follows:

7. (Due February 13) Show, step by step, how the grammar with rules S → ε and S → 0S1 will generate the word 000111.

8. (Due February 20) On the example of the automaton from Homework 4, 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 101 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.

9. (Due February 20) Use a general algorithm to construct a (non-deterministic) pushdown automaton that corresponds to context-free grammar with the starting variable S and the following rules:

Show, step by step, how the word abba will be accepted by this automaton. Its derivation in the given grammar is straightforward: S → abA → abbaS → abba.

10. (Due February 27) Transform the grammar from Homework 9 into Chomsky normal form.

11. (Due March 5) Use the general algorithm to transform the following pushdown automaton into a context-free grammar. This automaton recognizes words of the type qa...aca...aq, where the number of a's in both halves of the word is the same. This automaton has 4 states:

The transitions are as follows: Show, step-by-step, how the resulting grammar will generate the sequence qacaq.

12. (Due March 12) Show, step by step, how the stack-based algorithm will transform the expression (1 − 2) * (7 + 2) into a postfix expression, and then how a second stack-based algorithm will compute the value of this postfix expression.

13. (Due March 12) Write a program that, given an arithmetic expression,

You can assume that all the numbers in the arithmetic expression are one-digit numbers, i.e., each of these numbers is either 0, or 1, or 2, ..., or 9. For example, your program should correctly process expressions like 2+3*4, but there is no need to process expressions like 11+22.

Comments:

14. (Due March 12) For the LL(1) grammar that we studied in class, with rules S → F; S → (S + F); and F → a;, show how the word ((a + a) + a) can be represented as uvxyz in accordance with the pumping lemma for context-free grammars. Show that the corresponding word uvvxyyz will be generated by this grammar.

15. (Due March 12) Prove that the language consisting of all the words that have equal number of a's and b's and exactly twice as many c's is not context-free.

16. (Due April 9) Design a Turing machine that, given a positive unary number n, add 2 to this number. Test it, step-by-step, on the example of n = 3.

Solution to Homework 16

17. (Due April 9) Design a Turing machine that, given a positive binary number n greater than or equal to 2, subtracts 2 from this number. Test it, step-by-step, on the example of n = 4.

Solution to Homework 17

18. (Due April 9) Use the general algorithm to transform a finite automaton from Homework 4 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.

Solution to Homework 18

19. (Due April 16) 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.

20. (Due April 16) As we discussed in a lecture, a Turing machine can be described as a finite automata with two stacks:

On the example a Turing machine that computes n + 1 for n = 2, show, step-by-step:

Solution to Homework 20

21. (Due April 16) Give two examples:

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

Solution to Homework 21

22. (Due April 23) Prove that the square root of 3 is not a rational number.

Solution to Homework 22

23. (Due April 23) 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?

Solution to Homework 23

24. (Due April 30) Reproduce the proof of the halting problem in all the necessary detail.

Solution to Homework 24