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

1. Construction

   1. Construct DFA;
   2. Construct NFA;
   3. Construct regular expression;
   4. Use closure properties.

2. 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.

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:

1. for each $i \geq 0, x y^{i} z \in A$,
2. $|y|>0$, and
3. $|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

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