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:

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:

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

(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^*$:

(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

(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$
2. $\epsilon$
3. $\phi$
4. $R_1 \cup R_2$
5. $R_1 \circ R_2$
6. $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$
2. $|y| \gt 0 $
3. $|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:

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

(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)
2. $|y| \gt 0 $ (the recursive path is not reflexible)
3. $|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.

(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$
2. $|vy| \geq 1$
3. $|vxy| \leq p$

(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$
2. $A \rightarrow a $ where $a \in \Sigma$
3. 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$)
2. Eliminate unit rules ($A \rightarrow B$)
3. 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)$