Undecidability

Let’s start the day with a table of decidability construction:

Language	Setbuilder	Proof Idea
$A_{DFA}$	$\{⟨M,w⟩\mid \text{M is a DFA and w is a string and m accepts w}\}$	Simulated DFA on input w
$A_{NFA}$	$\{⟨N,w⟩\mid \text{N is an NFA and N accepts w}\}$	Convert $N$ to an equivalent DFA by subset construction, use decider for $A_{DFA}$
$A_{REGEX}$	$\{⟨R,w⟩\mid \text{R is a REGEX and R matches w}\}$	convert $R$ to an equivalent NFA by prior Theorem, use $A_{NFA}$
$E_{DFA}$	$\{⟨D⟩\mid \text{D is a DFA and }\mathcal{L}(D)=\varnothing \}$	graph search to find path between start and accept states
$E{Q}_{DFA}$	$\{⟨D_1,D_2⟩\mid D_1,D_2\text{ DFAs and }\mathcal{L}(D_1)=\mathcal{L}(D_2)\}$	$D_{3\mid \mathcal{L}}$

Undecidability dictates that we should