Computability Homework.

QUICK LINK TO HOMEWORK ASSIGNMENTS:

General information

• Problem sets are worth 100 pts. in total unless noted otherwise.
• Each problem is worth 10 pts. unless noted otherwise.
• All problem numbers refer to the course text: Introduction to the Theory of Computation by Michael Sipser (PWS Publishing, ISBN: 053494728X).
• Please see the schedule for the due date of each assignment.
• Practice exercises should not be handed in. You may be tested on these during exams. Solutions to the practice exercises appear in the "SOLUTIONS AND DOWNLOADS" portion of the website.
• Each assignment is due at the beginning of class.
• Some changes and additions are possible, but all the problems listed will eventually be part of some assignment. Any changes will be announced.
• For late assignments read the lateness policy.
• Assignments right before exams have a less liberal late-policy, so solutions can be posted for studying.
• Please write your name and cunix email on the first sheet as well as any loose sheet.
• Please staple the homework before handing it in (don't count on a stapler being available in class).
• If you collaborate with other students, you must follow the collaboration policy and list everyone that you worked with.
• Homework comprises 25% of the final grade.

Homework 1: Automata and Regular Expressions

Practice Exercises

• Look at the first 9 exercises for chapter 0. Do all exercises which you are clueless about.
• 1.1
• 1.2
• 1.10
• Choose any 5 parts of 1.13
• 1.15

Problems

1. (15 pts) Give state diagrams for DFA's recognizing the following languages over Σ = {0,1}:
   1. {w | 4 ≤ |w| ≤ 6 }
   2. {w | w contains the substring 110101 }
2. (5 pts) Give the formal description for your DFA in (1a).
3. (15 pts.) Find a regular expression for each of the bitstring languages A, B, C defined as follows:

   A =

   {x | the final three bits of x are the same}

   B =

   {x | the number of 0's in x is divisible by 3} (NOTE: 0 is divisible by 3)

   C =

   {x | if x contains the substring 000 then n₀(x) = 3} (NOTE: n₀(x) is the number of 0's in x)

   
   
4. (15 pts.) Consider the languages A, B, C from the previous problem. Use egrep to solve the following puzzle. A secret message has been embedded in a file of bitstrings and words. The message consists of three words. To discover the first word, find the unique line whose bitstring is in A∩B. To discover the second word, find the unique line whose bitstring is in B∩C. To discover the third word, find the unique line whose bitstring is in C∩A. For each discovered word, give the egrep command (or command sequence) that you used to find the word. HINT: You can learn about egrep in this egrep mini tutorial. How can UNIX piping (functional composition with the pipe symbol |) be used with egrep to achieve set intersection? If you would like to try out egrep at home on a Windows machine, check out the links page (for Mac OS X it's part of the Developer Tools).
5. Draw a 3-state NFA for a*b*a*a and a 1-state NFA for b*. (NOTE: a*b*a*a denotes its generated language, and similarly for b*.)
6. (15 pts.) Construct a DFA with Σ = {0,1} accepting exactly those bitstrings whose 10th bit from the right end is 0. The answer will require many states (more than 100) so you should not draw it. Instead, you should come up with some clever notation that gives a precise formal description of the DFA.
7. Now draw an NFA for the same language as in the previous problem.
8. Gabriella's Problem - 15 pts. Let Σ = {(0,0),(0,1),(1,0),(1,1)} be the alphabet of all pairs of bits. We can identify Σ* with the set of all pairs of binary strings of equal length. For example, instead of clumsily writing the length-3 string (0,1)(1,1)(1,0) we'll use the notation (011,110) -where we're concatenating in each coordinate. Show that the language L = { (x,y) ∈ Σ*   |   2[x]₂ = [y]₂ } can be accepted by a DFA. In other words, the operation of multiplication by 2 can be simulated by a regular language.
9. EC 10 pts. Salman's problem - an application of automata theory to Computer Networks.

Homework 2: Automata Constructions

Practice Exercises

• 1.17
• 1.18

Problems

1. Draw an NFA for the regular expression (0∪1)*(000∪1111∪(010)+)+(0∪1)*
2. Sipser's problem 1.16(b). You should draw diagrams for the intermediate DFA's that arise before you get to the regular expression.
3. Sipser's problem 1.12 (b). You should label each states by the subset of {1,2,3} that is being represented.
4. Draw the minimal DFA for the language of all bitstrings x that when viewed as a base-2 number are divisible by 6, and show your intermediate work. I.e., apply the minimization procedure on any DFA you have for:

   L = { x ∈ {0,1}*   |   [x]₂ mod 6 = 0 }

5. Consider DFA's M₁ and M₂ accepting the languages L₁ and L₂. Recall that the symmetric difference of two sets is defined by A⊕B = A∪B- A∩B.
   1. Show constructively that there is a DFA M_⊕ accepting L₁⊕L₂ such that the number of states in M_⊕ is the number of states in M₁ times the number of states in M₂. Hint: the proof of theorem 1.12, Sipser p. 45.
   2. Explain why regular languages are closed under symmetric difference.
6. A homomorphism is a function which replaces every character in one language by a string, in the same way for every appearance of the character. For example,
   • start with the language {aab, bab}
   • define a homomorphism f by the replacement rules: a → 00, b &rarr 101
   • the resulting homomorphic image is f({aab, bab}) = {0000101, 10100101}
   Prove that regular languages are closed under homomorphisms.
7. Problem 1.32.a, Sipser.
8. Problem 1.41, Sipser.

Homework 3: Pumping Lemma, Context Free Languages

Practice Exercises

• Practice pumping lemma problems (NOT TO HAND IN!!!!!)
  • Worked out pumping lemma example.
  • Show that each of the following languages is not regular: (Hint: You may be able to avoid using the pumping lemma directly in a case or two.)
    1. { 0^l1^m2^l+m | l, m ≥ 0 }
    2. { 0^l1^m2ⁿ | l, m, n ≥ 0 such that l+m is not equal to n }
    3. { 0^100+m1ⁿ0ⁿ | m, n ≥ 0 }
    4. { 0ⁿ³ | n is a non-negative number }
    SOLUTION
• 2.1

Problems

1. Use the pumping lemma to show that the following languages are not regular (assume that the alphabet of each is {0,1}):
   1. { w   |   ∃ x ∃ n > 1 , such that w = xⁿ }
   2. { 0ⁿ   |   n is a perfect cube }
2. The ANAGRAMS operator on languages is defined by taking all rearrangements of letters of all strings in the language. For example, ANAGRAMS({hi,mom}) = {hi,ih,mmo,mom,omm}. Prove that regular languages are not closed under ANAGRAMS.
3. 1. (10 pts) Find a set of numbers S such that when viewed in binary the set is regular, but when viewed base-10 it is not. You should assume that every number is represented without leading 0's. Prove that the language is regular when viewed in binary.
   2. (EC 5 pts.) Prove the language is not regular when viewed base-10.
4. (15 pts.) Find context free grammars for each of the following bitstring languages:

   A =

   { 0ⁱ1^j0^k   |   i = j or j = k where i,j,k ≥ 0 }

   B =

   { 0ⁱ1^j   |   at least one quarter of the bits are 0 and at least one quarter are 1's }

   C =

   even length strings that are palindromic except at exactly one bit = { uAvv^RBu^R   |   u, v are arbitrary, and A, B are opposite bits }

5. I have a written a little program called cfgrep which is the anolog of egrep for context free grammars. You can learn about and download this program from my cfgrep page. There you will also find example problems using cfgrep from previous versions of this course.

   Now Consider the languages A, B, C from the previous problem. Use cfgrep to solve the following puzzle: A secret message has been hidden via a file containing all length 16 bitstrings, and a code book. The message consists of three words. To discover the first word do the following:

   • count the number of length-16 bitstrings which are in A and call this value n
   • go to line n in the code book, and find the revealed word
   For example, supposing there were 41,382 length-16 bitstrings which are in A, you would discover the word "whale" (not surprising in this Moby Dick based text). To discover the second word use the same method, but start from the set B. Similarly, you discover the third word by applying the method to C. For full credit you should write down the cfgrep commands used, the number of matches found (use the -c flag), and the final discovered message.

   HINTS:

   • The message reflects Zeph's opinion about the course.
   • Also, note that cfgrep differs from egrep in that the default behavior is matching the entire line. Thus you don't use ^ at the beginning or $ at the end of your expression.
   • cfgrep may give incorrect results if you use epsilons. I suggest getting rid of any epsilons for your cfgrep expression (this shouldn't affect the solutions because we aren't trying to match any empty strings).

Homework 4: Language Theoretic Proofs, Pushdown Automata, Turing Machines

Practice Exercises

• Here's another example of how to prove that a grammar generates a purported language.
• Here's an example of a Turing Machine acceptor for the language { aⁿbⁿcⁿ | n > 0 }. The example was created using a program that a former student B. J. Dweck under my guidance. If you would like to try to simulate the pictured example, or want to draw your own Turing Machine with the program, try it out.

Problems

1. Prove that the grammar

   S   →   ε   |   aSb

   generates the language { aⁿbⁿ   |   n ≥ 0 }.
2. Draw the state diagram for a deterministic PDA accepting the language { a^mbⁿ   |   m ≠ n with m, n &ge 0 }. A DPDA is a PDA where from every state and for every instruction there is no ambiguity as to which state to go to next and which action to take on the stack. More precisely:
   • for any state q ∈ Q, input symbol a ∈ Σ and tape symbol X ∈ Γ there is at most one instruction in δ(q, a, X)
   • furthermore, no more than one instruction should be defined in δ(q, ε, Y) and if such an instruction exists, then δ(q, a, Y) should not be defined for any input symbol a ∈ Σ
   • similarly, no more than one instruction should be defined in δ(q, a, ε) and if such an instruction exists, then δ(q, a, Y) should not be defined for any tape symbol Y ∈ Γ
   • finally, no more than one instruction should be defined in δ(q, &epsilon, ε) and if such an instruction exists, then no other edge should be defined from q
3. So far we have seen 4 equivalent models for the class of regular languages: DFA's, NFA's, regular expressions, and GNFA's. There is also a fifth model, called right linear grammars. A right linear grammar is a context free grammar G = (V, Σ, R, S ) where variables only appear as the right-most character in any rule. In other words any production X → w in the rule set R satisfies:
   • either no variables appear in the right hand side so w ∈ Σ^*
   • or a variable appears as the last character so w ∈ Σ^*V
   For example, a right linear grammar for all odd length bitstrings is

   S   →   0   |   1   |   00S   |   01S   |   10S   |   11S

   1. (5 pts) Give a right linear grammar for all the strings in {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}^* which represent base-10 numbers that are divisible by 3.
   2. (10 pts) Give a proof by construction that right linear grammars characterize regularity. In other words, show that all regular language are generated by right linear grammars, and that right linear grammars only generate regular languages.
4. Prove by induction that the right linear grammar given in the previous problem for the set of all odd-length bitstrings actually generates the claimed language. This proves rigorously that the language is regular.
5. Find PDA's for the following languages:
   1. L_a = all well-formed strings of parentheses and braces. For example you should accept &epsilon, [[]], [()[()]]([]), but not (][).
   2. L_b = { aⁱb^jc^k   |   i = j   or   j = k   and   i, j, k ≥ 0 }
6. Prove by construction that context free languages are closed under intersection with regular languages. HINT: Given a PDA M and a DFA A describe a construction which results in a PDA for L(M)∩L(A).
7. Prove that the language

   L₇ = { aⁱb^jc^k   |   i = j = k   and   i, j, k ≥ 0 }

   is not context free.
8. Prove that context free languages are NOT closed under intersection. HINT: try to obtain the language of the previous problem as an intersection of context free languages.
9. (15 pts) Draw the state diagram of a Turing Machine that accepts all strings over Σ = { a, b } with the same number of a's as b's.

Homework 5: Decidability

Practice Exercises

• Consider the algorithmic decision problem

  DFA_FIVENESS : Given a DFA A, decide if |L(A)| = 5.

  Show that DFA_FIVENESS is decidable by describing an appropriate Turing Machine.

  SOLUTION

• 3.1
• 3.5
• 3.6
• 3.7
• 3.8
• 4.1
• 4.3
• 4.4
• 4.5
• 4.6

Problems

1. Describe in Turing Machine pseudocode a decider for the following language:

   L₁ = { binary strings which represent prime numbers }

   You may use any of the deterministic models that suits you (i.e. you can assume several stacks, and allow a "stay" move, etc. )
2. Consider the algorithmic decision problem

   CFG_FIVENESS : Given a CFG G, decide if |L(G)| = 5.

   Show that CFG_FIVENESS is decidable by describing an appropriate Turing Machine.
3. Describe a very high level Nondeterministic Turing Machine algorithm (with as many tapes as you like) that solves the following decision problem:

   Given any bitstring x. Let n = |x| be the length of x and let m be the numerical value of x in binary. Decide if for some number j in the range [1, 2ⁿ], m = j ^j mod 2ⁿ.

   For full credit your algorithm should use heavy branching and result in significantly shorter computations than the "obvious" deterministic version. Explain why you are making use of non-determinism.
4. Show constructively that any 1-tape TM can be simulated by a 2-stack PDA. What can you conclude about the class of languages accepted by 2-stack PDA's?
5. The goal of this problem is to show that {0,1}^* is countable by demonstrating an explicit bijection with the positve naturals Z₊ = {1, 2, 3, 4, ... }. You'll be given a formula for a function f : Z₊ → {0,1}^* which is supposedly a bijection. Your job is to find a formula for the inverse and prove that it really is an inverse. For the formula f as well as your inverse, use the following notation:
   • s(m) denotes the function which converts any positive number to its unique reduced binary string representative. So for example, s(4) = 100 and s(9) = 1001.
   • n(x) is the inverse of s so denotes the unique positive number represented by non-empty x in binary. So for example n(110) = 6.
   • for any string x, denote the portion of x starting from the i'th character and ending in the j'th character by x[ i , j ]. If j > i, we take x[ i , j ] = ε For example, if x = 1100, x[ 1 , 3 ] = 110, x[ 2 , 4 ] = 100, and x[ 4 , 3 ] = &epsilon.
   And now the definition of f :

   f (m) = s(m)[ 2 , |s(m)| ]

   HINTS: You can test your formula against the following matlab code for f on CUNIX. The matlab version of n(x) is bin2dec. Strings in matlab are defined by single quotes, e.g. x = '01'. Concatenation in matlab is achieved as follows: to concatenate x = '01' with y = '110' simply write [ x y ].

Homework 6: Undecidability and NP-Completeness

Practice Exercises

Problems

1. Explain why no Turing machine decider exists for deciding whether an arbitrary Turing machine which is started on empty input, will eventually print the words "Wasssup??? Wasabe!!!" and then enter a halt state.
2. (15 pts.) Consider the following two algorithmic problems. One of them is decidable and the other isn't. For the decidable problem, describe (at a high level) a Turing machine decider and explain why it is a decider. For the the undecidable problem describe whether the problem is recognizable, co-recognizable, or neither, and justify.
   • First Algorithmic Problem: Given a non-deterministic Turing Machine M. Decide if M ever needs to use any branching on some input.
   • Second Algorithm Problem: Given a non-deterministic Turing Machine M, decide if M is deterministic.
   Recall that all deterministic TM's are also non-deterministic since "non" really means "not necessarily".
3. Show that the following language is in P:

   L₁ = { x # y # z # w   |   x, y, z, w represent binary numbers with the property x ^y mod z = w }

   HINT: 6¹⁰⁰⁰ = 6^{512 + 256 + 128 + 64 + 32 + 8} = 6⁵¹²6²⁵⁶6¹²⁸6⁶⁴6³²6⁸ = 6²⁹6²⁸6²⁷ 6²⁶6²⁵6²³ = ((((((((6²)²)²)²)²)²)²)²)² · (((((((6²)²)²)²)²)²)²)² · ((((((6²)²)²)²)²)²)² · (((((6²)²)²)²)²)² · ((((6²)²)²)²)² · ((6²)²)²
4. Show that the decision problem described in problem 3 of the previous homework is in NP. Hint: Ideas from the previous problem might come in handy.
5. Show that if P = NP then there is a polynomial time algorithm for solving the input/output variant of SAT. In other words given φ -an arbitrary instance of SAT, we will be able to find an actual truth-value assignment to the variables which causes the boolean expression φ to return TRUE, or report that no such truth-value assignment exists, and do so in polynomial time. HINT: Showing that the following problem is in NP may be helpful:

   GIVEN: A boolean expression φ on boolean variables x₁, ... , x_n and a partial truth-value assignment to the first k variables x₁, ... , x_k.

   DECIDE: Does there exist a truth-value assignment to the remaining variables x_k+1, ... , x_n which causes φ to be satisfied?

   Then try to discover the correct assignment by asking a series of questions each answerable by the above decision problem.
6. Show that the following problem is NP-complete: Given an abitrary boolean expression φ, decide if φ is satisfied for at least 13 truth assignments.