Theory of Computing

# 目的
この記事は、理論計算機科学の講義の自分用メモです。正規言語、オートマトン、チューリングマシン、計算可能性理論などを含みます。内容はIntroduction to the Theory of Computation (Sipser)に依拠します。

# Regular Languages

## Regular Languages
L is a regular language if
- There exists a deterministic finite automaton that accepts the language L
- There exists a nondeterministic finite automaton that accepts the launguage L
- There exists a regular expression such that L(r) = L

## Deterministic Finite Automaton
DFA is 5-tuple:
```math
M = (Q, Σ, δ, q_0,F) \
```
Where 
- $Q$ is the states of the DFA
- $\Sigma$ is the alphabet of the DFA
- $\delta$ is the transition function s.t. $\delta :(q, a) \rightarrow Q$ where $q ∈ Q$ and $a ∈ \Sigma$
- $q_0$ is the start state of the DFA such that $q_0 ∈ Q$
- $F$ is the final states of the DFA

## Nondeterministic Finite Automaton
Nondtereministic Finite Automata(NFA) is also 5-tuple:
```math
N = (Q, Σ, δ, q_0,F) \
```
Where 
- $Q$ is the states of the NFA
- $\Sigma$ is the alphabet of the NFA
- $\delta$ is the transition function s.t. $\delta :(q, a) \rightarrow \mathcal{P}(Q)$ where $q ∈ Q$ and $a ∈ \Sigma$, and $\mathcal{P}(Q)$ is the power set of $Q$
- $q_0$ is the start state of the NFA such that $q_0 ∈ Q$
- $F$ is the final states of the NFA

## Features of DFA and NFA
### Configuration
Configuration is 2-tuple, $(q, x)$ where $q ∈ Q$ and $x ∈ \Sigma^\ast$. Configuration is a helpful way to express status of DFA and NFA. $q$ is the current state of the DFA or NFA, and $x$ is the residual string to be consumed.
### Transition Relation
$|-_M$ is the binary relation holds two configurations of DFA or NFA M if and only if the machine M can pass from one to the other as a result of a single move
```math
(q,w)|-_M(q',w')
```
where $w=aw', a∈\Sigma, \delta(q,a)=q'$. 
As the next step, define the reflexive, transitive closure of $|-_M$, $|-_M^*$:
```math
(q,w)|-_M^\ast(q',w')
```
where $w=xw', x∈\Sigma^*, q'$ is a state that is yielded from $q$ by consuming $x$. 
Then, we can here define the definition of "acceptance" as follows:
Machine M accept the string $w ∈ \Sigma^\ast$ iff $(q',w')|-_M^\ast(q',w')$.

### Fact 1
```math
(q,xy)|-_M^\ast (p,y) ⇔(q,x)|-_M^\ast (p,\epsilon)
```
## Regular Operations
The class of regular languages is closed under "regular operations".
- Union
- Concatenation
- (Kleene) Star
## Regular Expressions
A regular expression (over an alphabet $\Sigma$) R is a string over the alphabet $\Sigma\cup \lbrace(, ),\circ,\cup,\ast,\phi,\epsilon\rbrace$ such that
1. $a$ for $a\in \Sigma$
1. $\epsilon$
1. $\phi$
1. $R_1 \cup R_2$
1. $R_1 \circ R_2$
1. $R^{\ast} $

## Pumping Lemma
If $A$ is a regular language, then there is a number $p$ (pumping length) where if  $s\in A$ and $|s| \ge p$ then there exist strings $x, y,z$ s.t.$s=xyz$ and:
1. $xy^iz \in A$
1. $|y| \gt 0 $
1. $|xy| \le p$

Intuitive Proof:
If A is a regular language, then there should be a DFA M such that accepts A. Suppose the number of states of $A$ is $p$. If the language has a string of length greater than $p$, there should be a "recursive" path in the DFA. Let the start state of the recursive path be $q_r$. Let $x,y,$ and $z$ be strings such that:
```math
\displaylines{
(q_0,x)|-_M^\ast (q_r,\epsilon) \\

(q_r,y)|-_M^\ast (q_r,\epsilon) \\

(q_r,z)|-_M^\ast (q_f,\epsilon) \\
}
```
where $q_f$ is a final state. 
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3636063/7d505645-bd8a-3373-284c-b84e69b7237c.png)
(https://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages)
Then we can say:
1. $xy^iz \in A$ (the recursive path can be used anytime)
1. $|y| \gt 0 $ (the recursive path is not reflexible)
1. $|xy| \le p$ (must visit the same state at most p steps by the pegionhole principle)

This lemma says: All strings in the language should meet the requirement. If we can find at least one string in the language that does not meet the pumping lemma, we can say **the language is not regular**.

# Context-free Language
L is a context free language if and only if:
- L can be generated by some context-free grammar
- L is accepted by some PDA

## Context-free Grammar
Context-free grammar is 4-tuple $G(V, \Sigma , R, S)$
- $V$: a finite set of variables
- $\Sigma$: a finite set of terminals ($V \cap \Sigma = \phi$)
- $R$: a finite set of rules. $R \subseteq (V \times (V\cup \Sigma)^\ast)$
- $S$: start variables

## Pushdown Automata
NFAs (or DFAs) with the stack are called Pushdown Automata(PDAs). Nondeterministic PDA $M$ is a 6-tuple $M = (Q, \Sigma, \Gamma, \delta, q_0, F)$
- $Q$: a finite set of states
- $\Sigma$: the alphabet of the input language
- $\Gamma$: the alphabet of the stack
- $\delta$: the transition function $\delta:Q\times \Sigma _\epsilon \times \Gamma _\epsilon \rightarrow \mathcal{P}(Q \times \Gamma)$
- $q_0$: the start state
- $F$: the final states
## Relationship between Context-free Language and PDA
A language L is context-free iff there is some PDA that recognizes L

## Context-free and Regular
Theorem: If a language L is regular, then L is context-free.


![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3636063/4a268be0-d9f6-b4fd-e8ae-177d9771dbc2.png)
(https://ianfinlayson.net/class/cpsc326/notes/10-pda)


## Pumping lemma for Context-free language
If a language $L$ is context-free, there is a pumping length, $p$, where if $s \in L$ and $s \geq p$, then there exists $u,v,x,y,z$ where $s=uvxyz$ and,
1. $uv^ixy^iz \in L$
1. $|vy| \geq 1$
1. $|vxy| \leq p$

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3636063/be8579c8-7969-f2ae-09cb-07416d2a48db.png)
(https://en.wikipedia.org/wiki/Pumping_lemma_for_context-free_languages)

## Chomsky Normal Form
If a context-free grammar has only rules in the following form, the context-free grammar is in Chomsky Normal Form:
1. $A \rightarrow BC$ where $B,C \in V$
1. $A \rightarrow a $ where $a \in \Sigma$
1. Only the rule that has the start variable in its lefthand side can contain $\epsilon$ in its lefthand side

All context free grammars can be converted into Chomsky normal form by following three steps:
1. Eliminate $\epsilon$ rules ($A \rightarrow \epsilon$)
1. Eliminate unit rules ($A \rightarrow B$)
1. Eliminate $A \rightarrow u_1 u_2 ... u_k$ where $u_k \in \Sigma$ and $k \geq 2$

## Closure of Context-free

Context-free languages are closed under
- Union ($Z \rightarrow S_1 | S_2$)
- Concatination($Z \rightarrow S_1  S_2$)
- Star($Z \rightarrow S | \epsilon $)

# Turing Machines
A Turing machine is a 7-tuple $(Q, \Sigma, \Gamma, \delta, q_0, q_{accept},q_{reject})$ where

- $Q $ is a finite set of states
- $\Sigma$ is the alphabet of the input
- $\Gamma$ is the alphabet of the tape
- $q_0$ is the start state
- $q_{accept}$ is a finite set of the accpet states
- $q_{reject}$ is a finite set of the reject states

The results of Turing machines are categolized as:
- Accept
- Reject
- Loop

Turing machine can loop forever.

## Turing recognizable
A language is Turing-recognizable if there is some Turing machine that accepts the language and may not halt with the complement of the language.
## Turing decidable
A language is Turing-recognizable if there is some Turing machine that decides the language. That is, the Turing machine accepts if a string is in the lanugage. Otherwise, rejects.
## Turing unrecognizable
If a language is in Turing-recognizable but not in Turing decidable, then the complement of the lanugage is Turing unrecognizable (this means if a language is in Turing recognizable and its complement is also in Turing-recognizable, then the language is in Turing-decidable).
Let's think about the complement of the halt problem. The halt problem is Turing-recognizable. The complement of the halt problem is {$\<A,w\>$|$A$ is a Turing machine and loops on input $w$}. This language cannot be accepted any Turing machines. Then it is Turing-unrecognizable.

## Examples of Decidable Languages
The following languages are decidable:
- $A_{DFA}$ {$\<D,w\>$|$D$ is a DFA and accepts string $w$}
- $A_{NFA}$ {$\<N,w\>$|$N$ is a NFA and accepts string $w$}
- $A_{REX}$ {$\<R,w\>$|$R$ is a regular expression and generates string $w$}
- $EQ_{DFA}$ {$\<D_1,D_2\>$|$D_1$ and $D_2$ are DFAs and $L(D_1)= L(D_2)$}
- $E_{DFA}$ {$\<D\>$|$D$ is a DFA and accepts string $ L(D) = \phi$}
- $A_{CFG}$ {$\<G,w\>$|$G$ is a context-free grammar and generates string $w$}

## Examples of Undecidable Languages
The following languages are undecidable:
-  $A_{TM}$ {$\<M,w\>$|$M$ is a Turing machine and accepts string $w$}
-  $E_{TM}$ {$\<M,w\>$|$M$ is a Turing machine and $ L(M) = \phi$}
-  $EQ_{TM}$ {$\<M_1,M_2\>$|$M_1$ and $M_2$ are Turing machines and $L(M_1)= L(M_2)$}
-  $HALT_{TM}$ {$\<M,w\>$|$M$ is a Turing machine and halts on string $w$}

## Mapping Reducibility
### Computable Function
A function $f:\Sigma ^{\star} \rightarrow \Sigma ^{\star}$ is a computable function if some Turing machine M, on every input $w$ halts with just $f(w)$ on its tape.
### Mapping Reducible
A language A is mapping reducible to a language B denoted $A \leq _{m} B$, if there is a computable function $f:\Sigma ^{\star} \rightarrow \Sigma ^{\star}$ where for every $w$, $w \in A$ iff $f(w) \in B$. $f$ is called a reduction of $A$ to $B$.
- If $A \leq _{m} B$ and $B$ is Turing-decidable, then $A$ is Turing-decidable
- If $A \leq _{m} B$ and $A$ is Turing-undecidable, then $B$ is Turing-undecidable
- If $A \leq _{m} B$ and $B$ is Turing-recognizable, then $A$ is Turing-recognizable
- If $A \leq _{m} B$ and $A$ is Turing-unrecognizable, then $B$ is Turing-unrecognizable

# Time Complexity
## Time Complexity of Turing machines
### Time Complexity
Let M be a deterministic Turing machine that halts on all inputs. The running time or time complexity of $M$ is the function: $f:\mathbb{N} \rightarrow\mathbb{N}$ where $f(n)$ is the muximum number of steps that $M$ uses on any input of length $n$.

### Time Complexity Class
Let $t:\mathbb{N} \rightarrow\mathbb{N}$ be a function. The time complexity class, $TIME(t(n))$ is:
$TIME(t(n))=${$L$ | $L$ is a language that can be decided by some deterministic Turing machine in time $O(t(n))$}
Similrlly, $NTIME(t(n))$ is:
$NTIME(t(n))=${$L$ | $L$ is a language that can be decided by some nondeterministic Turing machine in time $O(t(n))$}

## Class P
$P=U_{k \geq 0}TIME(n^k)$
## Class NP
$NP=U_{k \geq 0}NTIME(n^k)$