Lab 10

Exercise 01

Let $A=\{⟨M⟩\mid \text{M is a DFA that doesn’t accept any string containing an odd nmber of 1s}\}$

Show that $A$ is decidable.

Construct $M_{1}st.\mathcal{L}(M_1)$ is only strings with an odd number of ones. Construct $M_{2}st.\mathcal{L}(M_2)=\mathcal{L}(M_1)\cap \mathcal{L}(M)$. Now we can feed to $E_{dfa}$

---

Exercise 02

Given: We have a theorem (Sipser 5.13) that $AL{L}_{CFG}=\{⟨G⟩\mid \text{G is a CFG and }\mathcal{L}(G)={\Sigma }^{\ast }\}$. (You don’t need to prove this; Sipser has done it for us.)

Use this theorem to prove the following:

Let $E{Q}_{CFG}=\{⟨A,B⟩\mid A,B\text{ are CFGs and }\mathcal{L}(A)=\mathcal{L}(B)\}$. Show that $EQ$ is undecidable.

Hint: use reduction and proof by contradiction

To prove that $E{Q}_{CFG}$ is undecidable, we will show that if it were decidable, then we could decide $AL{L}_{CFG}$, which we know is undecidable.

1. We assume that there exists a Turing machine $M_{EQ}$ that decides $E{Q}_{CFG}$.

2. We then construct a Turing machine $M_{ALL}$ that decides $AL{L}_{CFG}$ using $M_{EQ}$ as follows:

We are given a CFG $G$ and, we want to determine if $\mathcal{L}(G)={\Sigma }^{\ast }$.

• we construct CFG $G^{\prime }$ that generates ${\Sigma }^{\ast }$ (we make grammar that accepts all strings)
• we run $M_{EQ}$ on the pair $⟨G,G^{\prime }⟩G,G^{\prime }⟩$
• If $M_{EQ}$ accepts, then $\mathcal{L}(G)=\mathcal{L}(G^{\prime })={\Sigma }^{\ast }$, so $M_{ALL}$ accepts
• If $M_{EQ}$ rejects, then $\mathcal{L}(G)\ne \mathcal{L}(G^{\prime })={\Sigma }^{\ast }$, so $M_{ALL}$ rejects

3. this means that for $M_{ALL}$, it correctly decides $AL{L}_{CFG}$. The problem, however, is that this contradicts the theorem that $AL{L}_{CFG}$ is undecidable.

4. And thus, this means that our initial assumption that $M_{EQ}$ exists is false. Therefore, $E{Q}_{CFG}$ must be undecidable $■$

---

Exercise 03

Show that if $A$ is Turing-recognizable and $A{\le }_m\bar{A}$, then $A$ is decidable. decidable.

We can show that $A$ is decidable by constructing a Turing machine $M$ that decides $A$.

1. We first must note that since $A$ is a Turing-recognizable language, there exists a Turing Machine $M_A$ that recognizes $A$.
2. Then, we can use the fact that $A{\le }_m\bar{A}$ to construct a Turing machine $M$ that decides $A$ as follows:
   • Let $f$ be a computable mapping reduction such that $w\in A⟺f(w)\in \bar{A}$
   • On input $w$, our Turing-Machine $M$ completes the following:
     • Compute the $f(w)$
     • Run $M_A$ on the input $f(w)$
     • If $M_A$ accepts $f(w)$, then $f(w)\in A$, which means $w\notin A$, and thus $M$ rejects.
     • If $M_A$ does not accept $f(w)$, then $f(w)\notin A$, which means $w\in A$, so $M$ accepts
3. The TM $M$ always halts because it either accepts or rejects for any input $w$. Therefore, $A$ is decidable. $■$

---

Exercise 04

Recall what we’ve learned about relations.

Let $R$ be a binary relation on a set $A$.

$R$ is reflexive if for all $x\in A,xRx$.

$R$ is symmetric if for all $x,y\in A,xRy\Rightarrow yRx$.

$R$ is transitive if for all $x,y,z\in A,(xRyandyRz)\Rightarrow xRz$

$R$ is an equivalence relation if $A$ is nonempty and $R$ is reflexive, symmetric and transitive.

We say language $A$ is mapping reducible to language $B$, and we write $A{\le }_{m}B$, if there is some function $f$ such that $w\in A\iff f(w)\in B$

Show that the relation ${\le }_m$ is transitive.