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:

• you may immediately see how to convert, e.g., a context-free grammar into a Chomsky normal form,
• but if someone gives you a more complex case, you will have to use the algorithm.

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

• Of course, if someone gives you a list of 4 numbers on the test, you can sort them yourself easily.
• The purpose of the question was that you show that you understand mergesort, quicksort etc., not that you sort 4 numbers.

• If after you show that you understand the algorithm you also provide a simpler answer -- great,
• but not instead of following the algorithm.

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

1.1. Use the same ideas to describe an automaton for homework numbers. A homework number should start with a digits, it can be followed by digits and letters. For example, 12 and 12a should be accepted, while a1 should be rejected.

A natural idea is to have 3 states:

• the start state S,
• the state V indicating we have a valid homework number, and
• the state E indicating that this is an error.

• from S, any digit lead to state V, any other symbol leads to state E;
• from V, any digits and any letter lead to state V, any other symbol (e.g., ?) leads to state E;
• from E, any symbol leads back to E.

1.2. Trace, step-by-step, how the finite automaton from Part 1.1 will check whether the following two words (sequences of symbols) are valid homework numbers:

• the word 1a (which this automaton should accept) and
• the word a1 (which this automaton should reject).

1.3. Write down the tuple <Q, Σ, δ, q₀, F> corresponding to the automaton from Part 1.1:

• Q is the set of all the states,
• Σ is the alphabet, i.e., the set of all the symbols that this automaton can encounter; for simplicity, consider only three symbols: 1, a, and question mark ?;
• δ: Q x Σ → Q is the function that describes, for each state q and for each symbol s, the state δ(q,s) to which the automaton that was originally in the state q moves when it sees the symbol s (you do not need to describe all possible transitions this way, just describe two of them);
• q₀ is the starting state, and
• F is the set of all final states.

1.4. For each automaton A, let L_A denote the language of all the words accepted by this automaton, i.e., of all the words for which this automaton ends up in a final state. In class, we learned a general algorithm that:

• given two automata A and B that correspond to languages L_A and L_B,
• constructs two new automata for recognizing, correspondingly, the union and intersection of languages L_A and L_B.

• the automaton from Part 1.1 as Automaton A, and
• an automaton for words containing only digits as Automaton B.

• from n, any digit leads to n, any other symbol leads to w;
• from w, every symbol leads back to w.

Send solutions to Problem 1 to:

• Ian Flores if you are in the 12 pm section;
• Garab Dorji if you are in the 3 pm section.

Solution to Problem 1

2. (Due September 11)

• Use the general algorithm that we learned in class to design a non-deterministic finite automaton that recognizes the language 1(1 U a)* of all the words that start with 1 followed by symbols 1 and a.
  • 1 and a are languages consisting of only one 1-symbol word each: a is a language consisting of a single 1-symbol word a; 1 is a language consisting of a single 1-symbol word 1, etc.;
  • for any two languages C and D, the notation CD means concatenation;
• transform the resulting non-deterministic finite automaton into a deterministic one.

Send solutions to Problem 2 to:

• Monjur Bin Shams if you are in the 12 pm section;
• Garab Dorji if you are in the 3 pm section.

Solution to Problem 2

3. (Due September 11) Apply the general algorithm for transforming the finite automaton into a regular language (i.e., a language described by a regular expression) to Automaton B from Problem 1.4. For simplicity, assume that we only have symbols 1, a, and ?. Eliminate first the state n, then the state w.

Send solutions to Problem 3 to:

• Monjur Bin Shams if you are in the 12 pm section;
• Garab Dorji if you are in the 3 pm section.

Solution to Problem 3

4. (Due September 18) Write and test a method that simulates a general finite automaton. Your program should enable the computer to simulate any given finite automaton and then to simulate, for any given word, step-by-step, how this automaton decides whether this word is accepted by the automaton.

The input to this method should include the full description of the corresponding finite automaton:

• the number N of states; these states are q₀, ..., q_{N − 1}; we assume that q₀ is the start state; for simplicity, we describe the states by the corresponding integers 0, ..., N;
• the number M of symbols; these symbols are s₀, ... s_{M − 1}; for simplicity, we describe the symbols by the corresponding integers 0, ..., M;
• an integer array state[n][m] whose elements describe to what state the finite automaton moves if it was in the state q_n and sees the symbol s_m; and
• a boolean array final[n] whose elements describe, for each state q_n, whether this state is final or not.

Turn in:

• a file containing the code of the method, and
• a file containing the result of testing this method.

Send solutions to Problem 4 to:

• Ian Flores if you are in the 12 pm section;
• Monjur Bin Shams if you are in the 3 pm section.

5. (Due September 18) No matter how hard you study (S), you need some rest (R). Ideally, you should study no more 8 hours a day, with at least 16 hours remaining, i.e., you should have twice as much time to rest as to study. Prove that the following language is not regular: the language L of all sequences of Ss and Rs in which there are at least twice as many Rs as Ss. For example, the word SRSRRRR is in the language L, while the word SRSRR is not in L.

Send solutions to Problem 5 to:

• Ian Flores if you are in the 12 pm section;
• Monjur Bin Shams if you are in the 3 pm section.

Solution to Problem 5

6. (Due September 18) Show, step by step, how the following pushdown automaton -- that checks whether a word consisting of letters S and R corresponds to a situation in which there are at least twice as many rest hours as study hours -- will accept the word RSR. This pushdown automaton has three main states:

• the starting state s,
• the working state w, and
• the final state f,

In the stack, in addition to the bottom symbol $, we have:

• either one or several Ns -- indicating the difference between twice the number of study hours and the number of rest hours so far (if this difference is positive),
• or one or several Rs -- indicating the difference between the number of rest hours and twice the number of study hours (if this difference is positive).

• From s to w, the transition is ε, ε → $.
• From w to f, the transition is: ε, ε → ε.
• From f to f, we have two transitions: ε, R → ε and ε, $ → ε.

• If we see the symbol R and $ is on top of the stack, we keep the dollar sign and add R to the stack, i.e., we have transition R, $ → $ that brings us to an intermediate state a₁, and then the transition ε, ε → R that brings us back to the working state.
• If we see the symbol R and R is on top of the stack, we keep the top R and add another R to the stack, i.e., we have transition R, R → R that brings us to an intermediate state a₂, and then the transition ε, ε → R that brings us back to the working state.
• If we see the symbol R and N is on top of the stack, we delete the top N, i.e., we have transition R, N → ε.
• If we see the symbol S and $ is on top of the stack, we keep the dollar sign and add two Ns to the stack, i.e., we have transition S, $ → $ that brings us to an intermediate state a₃, then the transition ε, ε → N that brings us to an intermediate state a₄, and then the transition ε, ε → N that brings us back to the working state.
• If we see the symbol S and N is on top of the stack, we keep the top N and add two more Ns to the stack, i.e., we have transition S, N → N that brings us to an intermediate state a₅, then the transition ε, ε → N that brings us to an intermediate state a₆, and finally the transition ε, ε → N that brings us back to the working state.
• If we see the symbol S and R is on top of the stack, we first delete the top R from the stack, i.e., we have transition S, R → ε, and move to an intermediate state a₇.
  • If in this state, we see R on top of stack, we delete this R and go back to the working state; the transition is ε, R → ε
  • if in this state, we see $ on top of the stack, we add N, i.e., first we apply the transition ε, $ → ε and go to the intermediate state a₈, and then we apply the transition ε, ε → N, and go to the working state.

Send solutions to Problem 6 to:

• Ian Flores if you are in the 12 pm section;
• Monjur Bin Shams if you are in the 3 pm section.

Solution to Problem 6

7. (Due September 18) Show, step by step, how the following grammar describing valid homework numbers will generate the expression 1ab. In this grammar, D stands for digit, L stands for letter, S stands for statement. The rules are:

• D → 0
• ...
• D → 9
• L → a
• ...
• L → z
• S → D
• S → SD
• S → SL

Send solutions to Problem 7 to:

• Ian Flores if you are in the 12 pm section;
• Monjur Bin Shams if you are in the 3 pm section.

Solution to Problem 7

8. (Due September 25) In the corresponding 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.

• On the example of the automaton B from Homework 1.4, show how this algorithm will generate the corresponding context-free grammar. Similarly to Homework 3, assume that we only have symbols 1, a, and ?.
• On the example of the word 111 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.

Send solutions to Problem 8 to:

• Ian Flores if you are in the 12 pm section;
• Garab Dorji if you are in the 3 pm section.

Solution to Problem 8

9. (Due September 25) 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 expression 1ab will be accepted by this automaton.

Send solutions to Problem 9 to:

• Ian Flores if you are in the 12 pm section;
• Garab Dorji if you are in the 3 pm section.

Solution to Problem 9

10. (Due October 9) Transform the grammar from Homework 7 into Chomsky normal form. Assume that we are only using digit 1 and letter a.

Send solutions to Problem 10 to:

• Monjur Bin Shams if you are in the 12 pm section;
• Garab Dorji if you are in the 3 pm section.

Solution to Problem 10

11. (Due October 9) 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 RSR.

Send solutions to Problem 11 to:

• Monjur Bin Shams if you are in the 12 pm section;
• Garab Dorji if you are in the 3 pm section.

Solution to Problem 11

12. (Due October 16) For the grammar described in Homework 7, show how the expression 1ab 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.

Send solutions to Problem 12 to:

• Ian Flores if you are in the 12 pm section;
• Monjur Bin Shams if you are in the 3 pm section.

Solution to Problem 12

13. (Due October 16) A perfect arrangement would be to have 8 hours of study (S), 8 hours of rest (R), and 8 hours of sleep (P). Show that the language of all the words that have equal number of Ss, Rs, and Ps is not context-free.

Send solutions to Problem 13 to:

• Ian Flores if you are in the 12 pm section;
• Monjur Bin Shams if you are in the 3 pm section.

Solution to Problem 13

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

Send solutions to Problem 14 to:

• Ian Flores if you are in the 12 pm section;
• Garab Dorji if you are in the 3 pm section.

Solution to Problem 14

15. (Due October 23) Design a Turing machine that, given a unary number n which is larger than or equal to 4, subtracts 4 from this number. Test it, step-by-step, on the example of n = 5.

Send solutions to Problem 15 to:

• Ian Flores if you are in the 12 pm section;
• Garab Dorji if you are in the 3 pm section.

Solution to Problem 15

16. (Due October 23) Design a Turing machine that, given a binary number n, adds 16 to this number. Test it, step-by-step, on the example of n = 0.

Send solutions to Problem 16 to:

• Ian Flores if you are in the 12 pm section;
• Garab Dorji if you are in the 3 pm section.

Solution to Problem 16

17. (Due October 23) Use the general algorithm to transform a finite automaton B from Homework 1.4 -- as simplified in Homework 3, into a Turing machine. Show step-by-step, on an example of a word 1a, how this word will be processed by your Turing machine.

Send solutions to Problem 17 to:

• Ian Flores if you are in the 12 pm section;
• Garab Dorji if you are in the 3 pm section.

Solution to Problem 17

18. (Due November 6) As described in the corresponding lecture, every grammar obtained from a finite automaton is LL(1). For the grammar from Homework 8, build the corresponding table.

Send solutions to Problem 18 to:

• Monjur Bin Shams if you are in the 12 pm section;
• Garab Dorji if you are in the 3 pm section.

Solution to Problem 18

19. (Due November 6) Write a program that, given an arithmetic expression,

• first transforms it to a postfix form, and then
• computes its value (by using the stack-based algorithms that we recalled in class).

Comments:

• as with all programming assignments for this class, submit a file containing the code, and a file containing an example of what this program generates on each step;
• ideally, use Java, but if you want to write it in some other programming language, check with the TA that it is OK; usually, C or C++ are OK.

Send solutions to Problem 19 to:

• Monjur Bin Shams if you are in the 12 pm section;
• Garab Dorji if you are in the 3 pm section.

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

• the right stack contains, on top, the symbol to which the head points; below is the next symbol to the right, then the next to next symbol to the right, etc.;
• the left stack contains, on top, the symbol directly to the left of the head (if there is a one), under it is the next symbol to the left, etc.

• how each state of the corresponding Turing machine can be represented in terms of two stacks, and
• how each transition from one state to another can be implemented by push and pop operations.

Send solutions to Problem 20 to:

• Ian Flores if you are in the 12 pm section;
• Monjur Bin Shams if you are in the 3 pm section.

Solution to Problem 20

21. (Due November 20) Write and test a method that simulates a general Turing machine. Your program should enable the computer to simulate any given Turing machine for accepting-rejecting and then to simulate, for any given word, step-by-step, how this Turing machine decides whether this word is accepted or not.

The input to this method should include:

• the number N of states q₀, ..., q_{N − 1}; we assume that q₀ is the start state, that the last-but-one state q_{N − 2} is the accept state, and the last state q_{N − 1} is the reject state;
• the number M of symbols s₀, ... s_{M − 1}; we assume that s₀ is the blank state _;
• an integer array state[n][m] that describes to what state the head of the Turing machine changes if it was in the state q_n and sees the symbol s_m;
• an integer array symbol[n][m] that describes what symbol should be on the tape after the head in the state q_n sees the symbol s_m (it may be the same symbol as before, or it may be some other symbol written by the Turing machine);
• a character array lr[n][m] that describes, for each state q_n and for each symbol s_m, whether the head moves to the left (L), or to the right (R), or stays in place (blank symbol);
• the integer array of a large size describing the original contents of the tape, i.e., what symbols are written in each cell.

Your program should simulate 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.

Send solutions to Problem 21 to:

• Ian Flores if you are in the 12 pm section;
• Garab Dorji if you are in the 3 pm section.

22. (Due November 20) Give two examples:

• an example of computation time which makes an algorithm feasible according to the formal definition but not practically feasible, and
• an example of computation time for which the corresponding algorithm is practically feasible, but not feasible according to the formal definition.

Send solutions to Problem 22 to:

• Ian Flores if you are in the 12 pm section;
• Garab Dorji if you are in the 3 pm section.

Solution to Problem 22

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

Send solutions to Problem 23 to:

• Ian Flores if you are in the 12 pm section;
• Garab Dorji if you are in the 3 pm section.

Solution to Problem 23

24. (Due November 27) Prove that the cubic root of 40 is not a rational number.

Send solutions to Problem 24 to:

• Monjur Bin Shams if you are in the 12 pm section;
• Garab Dorji if you are in the 3 pm section.

Solution to Problem 24