**Lecture
19 (Reductions), 11/08/17**

**Concepts, definitions (in italics):**

- An algorithm for deciding if a given CFG generates a
given string.
- The
*languages*A-__DFA__, A-__NFA__, A-__REX__, A-__CFG__are decideable. - The
*languages*E-__DFA__, E-NFA, E-REX, E-__CFG__are decideable. - The
language of a given DFA/NFA/RE is empty if and only if there do not exist
any strings accepted (generated) by this DFA/NFA/RE. If there
exists any string accepted (generated) by this DFA/NFA/RE, then its
language is not empty.
- An algorithm for deciding if a given DFA accepts an
empty language
- An algorithm for deciding if a given CFG generates an
empty language
- The
*languages*EQ-__DFA__, EQ-NFA, EQ-REX are decideable. - An algorithm for deciding whether two DFAs are
equivalent.
**S1 = S2**iff their symmetric difference is empty- The
*symmetric difference*of S1 and S2 is (**S1 - S2) U (S2 - S1)** - But this algorithm won’t work for EQ-CFG (which is not
decidable), because CFGs are not closed under negation
- It will turn out that EQ-CFG is not
decidable
- There are
*two*directions for using reductions to prove something decidable or not: *Positive*: If A reduces to B and B is decidable then A is decidable (saw last time)

(so B is decidable then a reduction from A to B can be used to create a decider for A*Negative (contrapositive)*: If A reduces to B and A is not decidable then B is not decidable (will see next)

(so if we know that A is not decidable, then the reduction from A to B can be used to prove that B is not decidable)

·
Theorem:
A_{TM} is not *decidable*

·
This
proof proceeds as follows:

1.
Show
that D = {M: M is a Turing machine which rejects M} is undecidable

2.
Show
a reduction from D to A_{TM}

3.
Conclude
that A_{TM }is not decidable

**Reading:**

- Chapter 4.1 through theorem 4.8; chapter 4.2 from p.207
(“an undecidable language”) through figure 4.21

**Skills:**

- Know new definitions, understand new concepts.
- Be able to prove that the languages A-DFA, A-NFA,
A-REX, A-CFG are decidable.
- Be able to prove that the languages E-DFA, E-NFA,
E-REX, E-CFG are decidable.
- Be able to prove that the languages EQ-DFA, EQ-NFA,
EQ-REX are decidable.
- Understand the two directions for using reductions (to
show that something is decidable, and for showing it isn’t)
- Understand the proof that A-TM is not decidable.

**Notes:**

**A****DFA**= {<M, w> : M is a DFA that accepts w}

**A****NFA**= {(<M, w> : M is a NFA that accepts w}

**A****REX**= {<B, w> : B is a regular expression that generates w}

They are all*decidable*- The algorithm
for deciding
**A****CFG**relies on the following facts:

Any CFG can be converted to one in Chomsky Normal form.

A CFG in Chomsky Normal form cannot have a derivation longer than*2n-1*for a string of length*n*.

**E****DFA**= {<M>: <M> is a valid DFA specification where L(B) = Ø}

**E****NFA**= {<M>: <M> is a valid NFA specification where L(B) = Ø}

**E****REX**= {B: <B> is a valid regular expression specification where L(X) = Ø}

They are all*decidable*

- The
algorithm for deciding
**E****DFA**relies on the following fact:

A DFA's language is not empty if and only if there is a path from the initial state to some final state.

- EDFA-decider
does the following on input (D):

1) syntax check, REJECT if fails

2) check if there is a path in D from the intial state
to any of the final states

3) if yes, then REJECT else ACCEPT

- ENFA-decider does the following on input
(N)

1) syntax check, REJECT if fails

2) D = NFA_DFA_converter (N)

3) Return EDFA-decider (D)

- EREX-decider does the following on input
(R)

1) syntax check, REJECT if fails

2) N = RE_NFA_converter(R)

3) Return ENFA-decider(N)

·
Algorithm for **E _{CFG}**:

1) (Init) For every rule with no variables on RHS,

2) (Loop) For every rule with no unmarked variables on RHS,

3) Repeat step 2 until we cannot mark any more variables.

4) If

**EQ****DFA**= { <A, B> : A, B are equivalent DFA’s ) }

**EQ****NFA**= { <A, B> : A, B are equivalent NFA’s ) }

**EQ****REX**= { <X , Y> : X,Y are equivalent REX’s ) }

They are all*decidable*

- The algorithm
for deciding
**EQ****DFA**relies on the following fact:

Given any sets S1 and S2, S1 = S2 iff both**S1 - S2**and**S2 - S1**are empty, or in other words

Given any sets S1 and S2, their*symmetric difference***(S1 - S2)****U (S2 - S1)**will be empty iff S1 = S2.

- EQDFA-decider does the following on input
(D1,D2)

1) syntax check, REJECT if fails

2) D3 = construct the description of DFA accepting L(D1) – L(D2)

3) D4 = construct the description of DFA accepting L(D2) – L(D1)

4) Run EDFA decider on D3, then
on D4

5) If both are ACCEPTED (i.e. they both have empty languages), then ACCEPT; else
REJECT

·
Proof
of undecidability of A_{TM}:

1. Let D be the following
language: D = {M: M is a Turing machine which rejects M}

2. Assume D is decidable

3. Since D is decidable, there
must exist a TM *M _{D}* deciding D

4. What should it return when
given ** M_{D}** as input? It must either accept or reject all
inputs, including

5. But both ACCEPT and REJECT
give a contradiction.

6. Therefore, our assumption was
wrong and D is not decidable

7. But D is reducible to A_{TM}:

D- DECIDER(M)

{

BOOL b = A-TM-DECIDER(M, M)

return !b

}

8.
Therefore,
the algorithm A_{TM} is not decidable, either.