Automata
Homeworks for the course CS 3350, Spring 2017

1. (Due January 19) Design an automaton that recognizes real numbers in Java (both fixed-point and floating-point ones), and check it on two examples:

2. (Due January 26) Use the algorithm that we learned on January 19, with pairs of states from two automata as states of the new deterministic automaton, to describe the automata recognizing the union and the intersection of the languages A and B corresponding to the following automata:

3. (Due January 26) Use the algorithms that we learned in class on January 24 to design a non-deterministic automaton recognizing the language (0 U 1)(0 U 1)*:

4. (Due February 2) Use the general algorithm that we learned in class to come up with a regular expression that describes all the words accepted by the following automaton:

5. (Due February 9) Let us consider the following automaton: the automaton from the Problem 4 accepts the following word: aabbaa.

6. (For extra credit, due February 9) Prove that the following language is not regular {anbncn, n = 0, 1, 2, ...} = {Λ, abc, aabbcc, aaabbbccc, ...}.

7. (Due February 16) 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: Add the letter d, o, and r to this automaton, and show, step-by-step, how this automaton will recognize the sequence doorrood.

8. (Due February 16, for extra credit) Modify the pushdown automaton described in Problem 7 so that the new automaton will recognize all palindroms, not only palindroms of the type wwR. For example, the word madam should be recognized by this palindrom. Show, on an example of a palindrom different from what we had in class, how your automaton will recognize this palindrim.

9. (Due February 16) In class, we considered a context-free grammar (CFG) that generates palindroms. This CFG has the following rules:

On an example of a palindrom different from what we considered in class, show, step-by-step, how this palindrom will be generated by this grammar.

10. (Due February 23) 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 1011 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.

11. (Due February 23) Use a general algorithm to construct a (non-deterministic) pushdown automaton that corresponds to the context-free grammar with the following rules:

On the example of the word doorrood, show step-by-step how this word will be recognized by the resulting pushdown automaton.

12. (Due March 7) Apply, step-by-step, the general algorithm for transforming a context-free grammar into Chomsky normal form to the following context-free grammar. This grammar generates both palindromes composed of letters a and b and words of the type anbn:

13. (Due March 2 for extra credit, due March 7 for regular credit) Apply, step-by-step, the general algorithm of converting a pushdown automaton to a context-free grammar to the following pushdown automaton. This pushdown automaton has four states:

The transitions are as follows:

14. (Due March 9) 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.

15. (Due March 9) Illustrate the pumping lemma for context-free grammars by showing how it will represent the word s = aaacbbb which is generated by the CFG with rules S → ε, S → a, S → b, S → c, S → aSb, S → bSa, and S → cSc, as uvxyz. Show, step-by-step, how the corresponding word uvvxyyz can be derived from this CFG.

16. (Due March 23) Write a program that, given an arithmetic expression,

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

17. (Due March 23) Design a Turing machine that, given a unary number n, adds 2 to this number. Test it, step-by-step, on some example.

18. (Due March 23) Design a Turing machine that, given a binary number n, adds 2 to this number. Test it, step-by-step, on some example.

19. (Due March 30) 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.

20. (Due March 30) 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:

21. (Due April 13) In the proof that the halting problem is not algorithmically solvable, we use a diagonal function
f(n) which was defined as follows:

Write down the first 3 values f(0), f(1), and f(2) of the diagonal function f(n) for the following case:

22. (Due April 20) Not all algorithms are feasible, but, unfortunately, we do not have a perfect definition is feasibility. Give two examples:

These examples must be different from what we had in class.