On this page:
1 Induction Practice
2 Mapping Reducibility If-and-only-if
3 Another Mapping Reducibility Problem
4 A Recognizable and Unrecognizable Problem

Homework 7

Last updated: Wed, 10 Nov 2021 23:47:13 -0500

Out: Thu Nov 4, 00:00 EST Due: Wed Nov 10, 23:59 EST

This assignment explores mapping reducibility and unrecognizability.

Homework Problems

  1. Induction Practice (5 + 5 = 10 points)

  2. Mapping Reducibility If-and-only-if (5 + 5 = 10 points)

  3. Another Mapping Reducibility Problem (8 points)

  4. A Recognizable and Unrecognizable Problem (5 + 5 = 10 points)

  5. README (2 point)

Total: 40 points

Submitting

Submit your solution to this assignment in Gradescope hw7. Please assign each page to the correct problem.

A submission must include a README containing the required information, in addition to the solution to the problems.

1 Induction Practice

Prove the following statements using proof by induction. Be sure to clearly state what recursively-defined object the induction is on, and that the rest of the proof exactly follows this choice.

Also, every step of the proof must include a clear justification. Any extraneous words will result in loss of points.

(If you are unsure about what any of this means, review the piazza notes on induction, HMU Chapter 1.4, and Sipser Chapter 0.4. Then either post on Piazza or attend office hours until things are clear.)

  1. \sum_{i=0}^m z^i=\frac{1-z^{m+1}}{1-z}

  2. If S \Rightarrow^*_G \alpha then \beta S\gamma \Rightarrow^*_G \beta\alpha\gamma, where S is a variable in some CFG G and \alpha,\beta,\gamma are strings that may contain either terminals or non-terminals of G.

2 Mapping Reducibility If-and-only-if

3 Another Mapping Reducibility Problem

Prove that the following language is undecidable. You must use mapping reducibility.

EQ_\textsf{CFG}=\left\{\left\langle G,H\right\rangle\mid G \textrm{ and } H\textrm{ are }\textsf{CFGs}\textrm{ and }L(G)=L(H)\right\}

4 A Recognizable and Unrecognizable Problem

  1. Prove that the PCP language is recognizable.

  2. Prove that \overline{PCP}, the complement of the PCP language, is not Turing-recognizable.