Theory Of Computability Notes

Personal final notes for CSE 105 Theory of Computability. Not comprehensive – only like a final exam cheat sheet.

Regular Expression

Precedence: \((R)\) → \(R^{*}\) → \(R_{1} R_{2}\) → \(R_{1} \cup R_{2}\)

\(\emptyset\) represents empty set; \(\epsilon\) represents empty string; \(R^+ \equiv RR^*\)

Proving closure

Given: What does it mean for L to be in class? e.g. \(L\)* a regular language, so given a DFA/NFA* \(M_L\)

WTS: The result of applying the operation to \(L\) is still in this class.

Construction: Build a machine that recognizes the result of applying the operation to \(L\). Start with description in English! e.g. Let DFA/NFA \(M=_\cdots\)* (w.r.t to* \(M_L\))

Correctness: Prove \(L(M) =\) result of applying operation to \(L\)

WTS 1: if \(w\) is in set then \(w\) is accepted by \(M\)
WTS 2: if \(w\) is not in the set then \(w\) rejected by \(M\).

Prove regularity

Construction
1. Construct DFA;
2. Construct NFA;
3. Construct regular expression;
4. Use closure properties.
Proof of correctness

WTS 1 if w is in L then w is accepted by ….; WTS 2 if w is not in L then w is rejected by …

To show a language L is

Recognizable

Show there is a TM M with L(M) = L.
Use closure properties.

Not recognizable

Prove that L is not decidable and that the complement of L is recognizable.
Use closure properties.

Decidable

Show there is a TM D that always halts and \(L(D) = L\); Find a decidable problem L’ and show L reduces to L’ Use closure properties.

Not decidable

Use diagonalization Find an undecidable problem L’ and show L’ reduces to L. Use closure properties.

	Regular Languages	CFL	Decidable Languages	Recognizable Languages
Union	✓	✓	✓	✓
Intersection	✓	X	✓	✓
Complement	✓	X	✓	X
Star	✓	✓	✓	✓
Concatenation	✓	✓	✓	✓

Pumping Lemma

If \(A\) is a regular language, then there is a number \(p\) (the pumping length) where if \(s\) is any string in \(A\) of length at least \(p\), then \(s\) may be divided into three pieces, \(s=x y z\), satisfying the following conditions:

for each \(i \geq 0, x y^{i} z \in A\),
\(|y|>0\), and
\(|x y| \leq p\).

Proving strategies

Structure
- Assume to the contrary that \(L\) is regular
- Let \(p\) be the pumping length give by the pumping lemma
- Let \(s\) be … (w.r.t. \(p\))
  - Because \(s\in L\) and \(|s|\ge p\), pumping lemma guarantees that \(s=xyz\) satisfying the three condition of the lemma
- [show that there’s no such valid division]
  - cases depending on what \(y\) contains
  - consider pump down
- If cannot prove directly, use closure properties

Minimum pumping length

Find the shortest string that can be pumped
If has union
- One side is described by the other side: ignore the union
- No: maximum of smallest pumping lengths of each individual language
If can not be pumped: use the string length + 1
Check if the lengths of strings have gaps

Language	Definition	Properties
\(A_\text{DFA}\)	{⟨M,w⟩ \| M is a DFA and M accepts w}	Decidable
\(A_\text{TM}\)	{⟨M,w⟩ \| M is a TM and M accepts w}	Undecidable, RE, not CoRE
\(E_\text{DFA}\)	{⟨M⟩\| M is a DFA and L(M)=∅}	Decidable
\(E_\text{TM}\)	{⟨M⟩\| M is a TM and L(M)=∅}	Undecidable, not RE, CoRE
\(EQ_\text{DFA}\)	{⟨M1,M2⟩\| M1 and M2 are DFAs and L(M1)=L(M2)}	Decidable
\(EQ_\text{TM}\)	{⟨M1,M2⟩\| M1 and M2 are TMs and L(M1)=L(M2)}	Undecidable, not RE, not CoRE
\(\text{Diag}\)	{⟨M⟩ \| M is a TM s.t. ⟨M⟩ is not in L(M)}	Undecidable, not RE, CoRE
\(\text{HALT}_\text{TM}\)	{⟨M,w⟩ \| M is a TM and M halts on input w}	Undecidable, RE, not CoRE

Mapping Reduction

Assume \(A<_m B\), i.e., there is a map reduction from \(A\) to \(B\). Then, we have

If \(B\) is RE, then \(A\) is RE
If \(B\) is coRE, then \(A\) is coRE
If \(B\) is decidable, then \(A\) is decidable
If \(A\) is undecidable, then \(B\) is undecidable
If \(A\) is not in RE, then \(B\) is not in RE
If \(A\) is not in coRE, then \(B\) is not in coRE

Proof of correctness: Need to show two directions