▼CS622:   Theory of Formal Languages
►Homework 11
On this page:
1 A Closed Operation for Decidable/  Recognizable Languages?
2 Practice with Mapping Reducibility
3 Big-O Practice
4 DFA->NFA Running Time
    contents  ← prev  up  next → 

Homework 11

Last updated: Wed, 1 May 2024 11:39:51 -0400

Out: Wed May 01, 12:00pm EST (noon) Due: Wed May 08, 12:00pm EST (noon)

This assignment continues to explore undecidability, via mapping reducibility, and starts to look at time complexity.

Homework Problems

  1. A Closed Operation for Decidable/Recognizable Languages? (8 + 8 = 16 points)

  2. Practice with Mapping Reducibility (16 points)

  3. Big-O Practice (12 points)

  4. DFA->NFA Running Time (14 points)

  5. README (2 points)

Total: 60 points

Submitting

Submit your solution to this assignment in Gradescope hw11. Please assign each page to the correct problem and make sure your solutions are legible.

A submission must also include a README containing the required information.

1 A Closed Operation for Decidable/Recognizable Languages?

The "Closed" Operation Practice Problem from Homework 3 introduced the \mathrm{NEG} operation.

  1. Prove that Turing-decidable languages are closed under \mathrm{NEG}.

    This theorem is needed to complete the undecidability proof in Practice with Mapping Reducibility, part 2, above.

    Specifically:

    • Give the if-then statement to be proved,

    • and then prove it.

      Remember that deciders require termination arguments. Also, an Examples Table as shown in class is required to "prove" that a machine recognizes some language.

  2. Now let’s think about whether Turing-recognizable languages are closed under \mathrm{NEG}.

    Specifically, answer the following:

    1. Give the If-Then statement that must be proved.

    2. Now sketch out a potential proof by giving a table of Statements and Justifications, where the last statement is the If-Then statement to be proved from above. It should be similar to part 1 above.

      You may run into difficulty when trying to work out the Examples Table justification step. Remember that the Examples Table must show all possible combinations of results from all of the Turing machines involved in your answer.

    3. Based on the Examples Table you created, comment on why using the same proof approach as in part 1 won’t work. That is, explain why Turing-recognizable languages might not be closed under the \mathrm{NEG} operation ...

2 Practice with Mapping Reducibility

In lecture, we learned a new way to prove undecidability using mapping reducibility.

Recall that showing mapping reducibility between two languages requires two steps:

  • creating a computable function between the two languages, and

  • showing that the appropriate if-and-only-if statement (which itself has two parts) holds for that computable function.

We then started to re-prove undecidability for some previously seen languages. For this problem, you’ll complete what we started for one of them.

Specifically, prove that E_\textsf{TM} is undecidable using mapping reducibility.

To do this you’ll need to show that A_\textsf{TM} is mapping reducible to \overline{E}_\textsf{TM}. This involves:

  1. understanding the computable function from class,

  2. giving the if-and-only-if statement that must be proved, for there to be a mapping reducibility between these two languages,

  3. and showing that the computable function from class satisfies this if-and-only-if requirement. Don’t forget that proving an if-and-only-if statement requires proving two separate statements. Further, the contrapositive must be used for the reverse direction.

After you’ve established mapping reducibility, complete the undecidability proof. As usual, the proof must be in the form of a Statements and Justifications Table. (You’ll also likely need to use some other theorems from lecture to complete the proof.)

3 Big-O Practice

Answer TRUE or FALSE for each statement below.

For each statement that is TRUE, give a value for c and n_0 that satisfies the inequality in the definition of big-O.

  1. n^{99} = 2^{O(n)}

  2. 420^{2n} = 2^{O(n)}

  3. n-420 = O(\log n)

  4. n\log n = O(\log n)

  5. 420+n = O(n)

  6. 420 = O(n^3)

4 DFA->NFA Running Time

When learning about regular languages, we defined an algorithm \texttt{convert} (in Homework 3) to convert a DFA, e.g., D = (Q_D,\Sigma,\delta_D,q_D,F_D), to an equivalent NFA, e.g., N = (Q_N,\Sigma,\delta_N,q_N,F_N), and we used this procedure in the deciders of several languages.

Compute the running time of the \texttt{convert} algorithm. Express your answer using big-O notation in terms a variable n = |Q_D| representing the number of states in the DFA. Is this a polynomial time algorithm?

Structure your solution according to the components of the DFA. In other words, your solution should say how many steps it takes to compute Q_N from Q_D, how many steps it takes to compute \delta_N from \delta_D, etc., and then add them all together. As another hint, to calculate this runtime, you want to be thinking about the size of each of the computed NFA parts, in comparison to their DFA counterparts.

    contents  ← prev  up  next →