Automata
Homeworks for the course CS 3350, Fall 2021

General comment. The main purpose of most homeworks is to show how well you understand the algorithms.

In many cases, the resulting finite automata, pushdown automata, and Turing machines can be simplified, but please first literally apply the algorithm so that we know that you can use it.

If in addition to this, you also show how to make the corresponding Turing machine or finite automaton or whatever more concise, nothing wrong with that, the TA may even give you some extra points (if she has time to grade these additional things). But the most important thing is to show that you can follow the algorithm.

For simple examples that we give you as homeworks:

So, it is important to learn how to follow the algorithm.

If you deviate from the algorithm, how do we know that you learned the algorithms? It was the same with sorting.

In general:

1. (Due September 2) In class, we designed automata for recognizing integers and real numbers.

1.1. Use the same ideas to describe an automaton for recognizing names of classes in Java. In Java, this name should start with a capital letter, and contain only letters, digits, or the underscore symbol. To describe an automaton, draw a picture like we did in class.

A natural idea is to have 3 states: start (s), correct class name (c), and error (e). Start is the starting state, c is the only final state. The transitions are as follows:

1.2. Trace, step-by-step, how this finite automaton will check whether the following two words (sequences of symbols) are correct names for Java classes:

1.3. Write down the tuple <Q, Σ, δ, q0, F> corresponding to this automaton:

1.4. Apply the general algorithm for union and intersection to:

For simplicity, in your automaton for recognizing the union and intersection of the two languages, feel free to assume that you only have symbols 0, a, A, underscore, and +.

Solution to Homework 1

2. (Due September 2)

Solution to Homework 2

3. (Due September 9) 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: s (= straight-A student) and e (= everyone else); s is the starting state, it is also the final state. The only two symbols are A and B. From s, A leads back to s, and B leads to e. From e, any symbol leads back to e.

Solution to Homework 3

4. (Due September 9) Prove that the following language is not regular {a2nbn, n = 0, 1, 2, ...} = {Λ, aab, aaaabb, aaaaaabbb, ...}.

Solution to Homework 4

5. (Due September 16) 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. Turn in:

Feel free to use Java, C, C++, Fortran, or any programming language in which the code is understandable.

6. (Due September 16) Show, step by step, how the following pushdown automaton will recognize a sequence ++−−. This pushdown automaton has two states:

The transitions are as follows:

Solution to Homework 6

7. (Due September 16) Show, step by step, how the grammar with rules S → ε and S → +S− will generate the word ++−−.

Solution to Homework 7

8. (Due September 16) In a lecture, we described an algorithm that, given a finite automaton, produces a context-free grammar -- a grammar that generate a word if and only if this word is accepted by the given automaton.

Solution to Homework 8

9. (Due September 16) Use a general algorithm to construct a (non-deterministic) pushdown automaton that corresponds to context-free grammar described in Problem 7. Show, step by step, how the word ++−− will be accepted by this automaton.

Solution to Homework 9

10. (Due October 7) Transform the grammar from Homework 7 into Chomsky normal form.

Solution to Homework 10

11. (Due October 7) Use the general algorithm to transform the pushdown automaton from Problem 6 into a context-free grammar. Show, step-by-step, how the resulting grammar will generate the word ++−−.

Solution to Homework 11

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

Solution to Homework 12

13. (Due October 14) 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. For simplicity, assume that the only arithmetic operations are addition +, subtraction −, and multiplication *.

Comments:

14. (Due October 21) 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.

Solution to Homework 14

15. (Due October 21) Prove that the language consisting of all the words that have equal number of +'s and −'s and exactly two times as many opening parentheses is not context-free.

Solution to Homework 15

16. (Due November 4) 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 = 2.

Solution to Homework 16

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

Solution to Homework 17

18. (Due November 4) Use the general algorithm to transform a finite automaton from Homework 3 into a Turing machine. Show step-by-step, on an example of a word AAA, how this word will be recognized by your Turing machine.

Solution to Homework 18

19. (Due November 4) 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 a binary number n = 4, show, step-by-step:

Solution to Homework 19

20. (Due November 11) 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.

21. (Due November 11) 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 November 11) 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 22

23. (Due November 18) Prove that the cubic root of 5 is not a rational number.

Solution to Homework 23