12. Modeling Computation

12.1. Languages and Grammars

Phrase-Structure Grammars

Vocabulary(Alphabet) $V$는 Symbol의 Element의 Finite nomempty set이다.
$V$ 위 Word(Sentence)는 $V$의 Element로 구성된 Finite length의 String이다.
$\lambda$의 경우 Empty string이나 Null string은 Symbol이 포함되지 않은 String을 의미한다.
모든 Word의 Set을 $V^\ast$로 표시하며 $V$ 위 Language는 $V^\ast$의 Subset이다.

대체 불가능한 Symbol을 Terminal, 그렇지 않은 Symbol을 Nonterminal이라고 하며 각각 $T,N$으로 표현한다.
$V^\ast$의 String에서 다른 String으로 교체할 수 있는 시점을 지정하는 규칙을 Grammar의 Production이라고 하며 Notation $z_0 \to z_1$으로 표시한다.
위 Notation은 $z_0$가 $z_1$으로 대체 가능하다는 것을 의미한다.
Start symbol은 $S$로 표기한다.

Phrase-structure grammar $G=(V,T,S,P)$는 Vocabulary $V$, $V$의 Subset $T$(Terminal), $V$의 Start symbol $S$, Production의 Finite set $P$로 구성되어 있다.
$V-T=N$($N$은 Nonterminal symbol)이며 $P$의모든 Production은 Left side에 최소한 하나의 Nonterminal을 포함하여야 한다.

팁

Example

$G=(V,T,S,P)$라고 할 때 $V=\{a,b,A,B,S\},T=\{a,b\}$이고 $S$는 Start symbol, $P=\{S\to ABa,A\to BB, B\to ab, AB\to b\}$일 때 $G$는 Phrase-structure grammar의 예시이다.

$G=(V,T,S,P)$가 Phrase-structure grammar라고 할 때 $w_0=lz_0r$이고 $w_1=lz_1r$이라고 할 때 $z_0\to z_1$가 $G$의 Production일 경우 $w_1$이 $w_0$로부터 Directly derivable이라고 하며 $w_0\Rightarrow w_1$으로 표현한다.
만약 $w_0\Rightarrow w_n$이라면 $w_n$이 $w_0$으로 부터 Derivable라고 말한다($w_0\Rightarrow w_1\Rightarrow \cdots \Rightarrow w_n$).
$w_0$로부터 $w_n$을 얻기 위해 사용된 Step을 Derivation이라고 한다.

팁

Example

앞 예시에서 String $Aaba$는 Directly derivable from $ABa$이다.
왜냐하면 $B\to ab$이기 때문이다.
$abababa$는 $ABa$로 부터 Derivable인데 그 이유는 $ABa\Rightarrow Aaba\Rightarrow BBaba\Rightarrow Bababa\Rightarrow abababa$이기 때문이다.

$G=(V,T,S,P)$가 Phrase-structure grammar일 때 $G$에 의해 생성된 Language는 $L(G)$로 표기하며 Starting state $S$로 부터 Derivable인 Terminal string들의 Set이다.
즉 $L(G)=\{w\in T^\ast \mid S \overset{\ast}{\Rightarrow}w\}$이다.

팁

Example

$G$를 Vocabulary $V=\{S,A,a,b\}, T=\{a,b\},P=\{S\to aA, S\to b, A\to aa\},S$의 Grammar라고 할 때 Grammar의 Language $L(G)$

• Solution
  Start state $S$로부터 Production $S\to aA, S\to b$를 사용하여 $aA, b$를 Derive할 수 있고 $A\to aa$를 이용하여 $aA$를 $aaa$로 Derive 가능하다.
  즉 $L(G)=\{b, aaa\}$이다.

팁

Example

Set $\{0^n1^n \mid n=0,1,2,\dots\}$을 생성하는 Phrase-structure grammar

• Solution
  두 개의 Production을 사용하여 0의 String 뒤에 같은 수의 1이 오는 모든 String을 생성할 수 있으며 이 때 Empty string도 포함된다.
  String의 시작에 0, 끝에 1을 추가하여 점진적으로 길어지는 String을 만들고 두 번째 규칙은 $S$가 $\lambda$임을 나타낸다.
  즉 $G=(V,T,S,P)$이며 $V=\{0,1,S\},T=\{0,1\}, S$는 Starting symbol, Production $P$는 $S\to 0S1, S\to \lambda$가 된다.

Types of Phrase-Structure Grammars

Phrase-structure grammer는 허용되는 Production의 Type에 따라 분류할 수 있다.

• Type 0 grammer
  Production 생성에 제한이 없다.
• Type 1 grammer(Context-sensitive grammer)
  $w_1\to w_2$ Form의 $w_1=lAr \land w_2=lwr$일 때 $A$는 Nonterminal symbol, $l, r$은 0개 이상의 Terminal 혹은 Nonterminal symbol이다.
  $S\to A$라는 Production을 가질 수 있는데 이 때 $S$는 다른 Production의 오른쪽에 나타날 수 없다.
• Type 2 grammer(Context-free grammer)
  $w_1$이 Nonterminal symbol일 때 $w_1\to w_2$ Form의 Production을 가질 수 있다.
• Type 3 grammer(Regular grammer)
  $w_1=A$이고 $w_2=aB \lor w_2=a$인 경우 $w_1\to w_2$ From의 Production을 가질 수 있다.
  이 때 $A, B$는 Nonterminal, $a$는 Terminal symbol이거나 혹은 $w_1=S \land w_2=\lambda$일 경우에도 가능하다.

Contect-sensitive grammer로 생성된 Language를 Context-sensitive language, Context-free language grammer로 생성된 Language를 Context-free language, Regular grammer로 생성된 Language를 Regular라고 부를 수 있다.

$w_1\to w_2$ From의 Production은 $w_1$의 길이가 $w_2$의 길이보다 작거나 같은 경우 Noncontracting(비축소적)이라고 한다.
모든 Type 1 grammer의 Production은 $S\to \lambda$를 제외한다면 Noncontracting이다.
이는 Context-free language의 Derivation 과정에서 String의 길이가 Nondecreasing이라는 뜻이다.($S\to \lambda$를 제외하고)
즉, Context-sensitive grammer에 의해 생성된 Language에 Empty string이 포함되기 위해서 $S\to \lambda$ Production이 Grammer의 일부여야 한다.
Context-sensitive grammer로 정의되는 다른 방법은 모든 Production이 Noncontracting이거나 Monotonic(단조적)일 때이다.
Noncontracting grammer의 Class는 Context-sensitive grammer의 Class와 동일하지 않으나 이 두 Class는 밀접히 Related이며 Noncontracting grammer는 Empty string $\lambda$를 포함하는 어떤 Language도 생성할 수 없다는 것을 제외하고 동일한 Language set을 정의한다는 것을 알 수 있다.

팁

Example

$\{0^m1^n \mid m,n=0,1,2,\dots\}$의 Phrase-structure grammer를 찾고 어떤 Type의 Language인지 기입

• Solution
  두 Grammer $G_1, G_2$를 이 Set에 생성하여 두 Grammer가 동일한 Language를 생성할 수 있음을 보여 Phrase-structre grammer를 찾는다.
  Grammer $G_1$은 Alphabet $V=\{S,0,1\};$ Terminal $T=\{0,1\};$ Prouduction $S\to 0S, S\to S1, S\to \lambda$가 Set을 생성한다.
  첫 번째 Production을 $m$번 사용할 경우 0이 $m$개 String의 시작에 추가되고, 두 번째 Production을 $n$번 사용할 경우 1이 $n$개 String의 끝에 추가된다.
  Grammer $G_2$는 Alphabet $V=\{S,A,0,1\};$ Terminal $T=\{0,1\};$ Production $S\to 0S, S\to 1A, S\to 1A, A\to 1, S\to \lambda$이다.
  $A\to 1$과 $A\to 1A, S\to 1A$로 $A$역시 위 $G_1$의 두 번째 Production과 동일하게 활용될 수 있다.
  마지막으로 이 Language의 경우 Type 3 language, 즉 Regular language이다.
  이유로 $G_2$가 Regular grammer이고 그 $G_2$로 생성되었기 때문이다.

요약하여 Table로 아래와 같이 나타낼 수 있다.

Type	Restrictions on Productions w1 →w2
0	No restrictions
1	(A\in N,l,r,w\in (N\cup T)^\ast \land w\not=\lambda) \to(w_1=lAr \land w_2=lwr); or w_1=S and w_2=\lambda as long as S is not on the right-hand side of another production
2	w_1=A, where A is nonterminal symbol
3	w_1=A \land (w_2=aB \lor w_2=a), where A\in N, B\in N, a\in T or w_1=S \land w_2=\lambda

Derivation Trees

Context-free grammer로 생성된 Language의 Derivation은 Ordered rooted tree를 사용하여 표현할 수 있으며 이를 Derivation(Parse) tree라고 한다.
Root는 Start symbol $S$를, Tree의 Internal vertex들은 Derivation step에서 발생하는 Nonterminal symbol을 나타낸다.
Tree의 Leaf의 경우 Terminal symbol을 나타낸다.
만약 $A\to w$라는 Production이 Derivation step에서 발생할 경우 $A$를 나타내는 Vertex들에는 $w$라는 Symbol을 왼쪽에서 오른쪽 순서대로 나타내는 Children vertex들을 가진다.

팁

Example

Hungry rabbit eats quickly에 대한 Derivation tree

• Solution\

팁

Example

Word $cbab$가 Grammer $G=(V,T,S,P), V=\{a,b,c,A,B,C,S\},T=\{a,b,c\}, S$는 Starting symbol, Production $P$는 $S\to AB, A=Ca,B\to Ba, B\to Cb, B\to b, C\to cb, C\to b$일 때 Word가 맞는 지 확인

• Solution
  쉽게 풀기 위해 하위에서 상위로 Parsing 할 수 있는데 이를 Bottom-up parsing이라고 한다.
  $cbab\gets Cab\gets Ab \gets AB \gets S$로 풀 수 있다.
  정석으로 상위에서 하위로 Parsing하는 것은 Top-down parsing이라고 한다.

Backus-Naur Form

Type 2 grammer를 지정하는 Notation 중 Backus-Naur form(BNF)가 존재한다.
모든 Production을 나열하는 대신 왼 쪽에는 단일 Nonterminal symbol을 놓고 같은 Nonterminal symbol이 있는 모든 것을 하나의 Statement로 결합한다.
Production에서 $\to$ 대신에 $::=$를 사용한다.
모든 Nonterminal symbol을 $<\ >$로 묶어 Production의 오른쪽 부분을 같은 Statement에서 나열하고 $|$를 사용하여 구분한다.

팁

Example

Production $A\to Aa, A\to a, A\to AB$을 Backus-Naur form으로 표현

• Solution
  $<A>::=<A>a|a|<A><B>$

팁

ALGOL 60에서 Indentifier는 Alphanumeric character로 구성되며 반드시 Letter로 시작해야 한다.
이러한 Rule을 Backus-Naur form으로 아래와 같이 나타낼 수 있다.

$<identifier>::=<letter>|<identifier><letter>|<identifier><digit> \\ <letter>::=a|b|\cdots|y|z \text{the ellipsis indicates that all 26 letters are included} \\ <digit> ::= 0|1|2|3|4|5|6|7|8|9$

12.2 Finite-State Machines with Output

이미 Output이 있는 Finite-state machine의 Formal definiton은 아래와 같다.
$M=(S,I,O,f,g,s_0)$을 Finite-state machine이라고 할 때 Finite state set $S$, finite input alphabet $I$, finite output alphabet $O$,$S$ transition function $f$(각 State와 Input pair에 대한 새로운 State를 할당하는 Function), Output function $g$(각 State와 Input pair에 대한 Output을 출력하는 Function), Initial state $s_0$로 구성된다.

$M=(S,I,O,f,g,s_0)$이 Finite-state machine일 때 State table을 사용하여 Transitional function, Output function $f,g$의 모든 State와 Input pair에 대해 나타낼 수 있다.

팁

Example

아래는 $S=\{s_0,s_1,s_2,s_3\}, I=\{0,1\}, O=\{0,1\}$인 Finite-state machine에 대한 State table이다.

State table 대신 나타낼 수 있는 방법으로는 Finite-state machine의 State diagram이며 아래 그림과 같다.\

Input string은 Transition function에 의해 결정된 일련의 State를 통해 Starting state를 이동시킨다.
Input string을 왼쪽에서 오른쪽으로 Symbol 별로 읽을 때, 각 Input symbol은 Machine을 한 State에서 다른 State로 이동시킨다.
각 Transition이 Output을 생성하기에 Input string은 Output string도 생성한다.

Input string이 $x=x_1x_2\dots x_k$라고 할 때 이 Input을 읽는 과정에서 Machine은 State $s_0$에서 $s_1$로 이동하며 $s_1=f(s_0,x_1), s_2=f(s_1,x_2),\cdots, s_k=f(s_{k-1},x_k)$가 되게 된다.
이 Transition의 순서는 Output string $y_1y_2\dots y_k$를 생성하며 $y_1=g(s_0,x_1),\cdots, y_k=g(s_{k-1},x_k)$가 되게 된다.
즉 Function $g$의 정의를 Input string에 확장할 수 있으며 $g(x)=y$로 표현할 수 있다.

팁

Example

Input string이 101011일 때 아래 그림에 의해 생성된 Finite-state machine의 Output string\

• Solution\

$M=(S,I,O,f,g,s_0)$를 Finite-state machine이라고 하고 $L\subseteq I^\ast$일 때 $M$이 $L$을 Recognize(Accepts)한다고 말할 수 있는 것은 Input string $x$가 $L$에 속할 때, $x$를 Input으로 주었을 때 $M$이 생성하는 마지막 Output bit가 $1$이 되는 경우 뿐이다.

12.3. Finite-State Machines with No Output

Set of Strings

$V$가 Vocabulary일 때 $A, B$가 $V^\ast$의 Subset이라고 가정할 때 $AB$($A$와 $B$의 Concatenation)은 $A$의 String $x$와 $B$의 String $y$로 이루어진 모든 String $xy$의 Set이다.

팁

Example

$A=\{0,11\}, B=\{1,10,110\}$일 때 $AB, BA$

• Solution
  $AB=\{01,010,0110,111,1110,11110\}, BA=\{10,111,100,1011,1100,11011\}$

팁

Example

$A=\{1,00\}$일 때 $A^n$($n=0,1,2,3$)

• Solution
  $A^0=\{\lambda\}, A^1=A^0A=\{1,00\}$이다.
  반복하여 $A^2=\{11,100,001,0000\}, A^3=\{111,1100,1001,10000,0011,00100,00001,000000\}$
  이 된다.

$A$가 $V^\ast$의 Subset일 때 $A$의 Kleene closure는 $A^\ast$로 표시하고 $A$에서 임의의 개수의 String을 연결한 Set($A^\ast=\bigcup^\infin _{k=0}A^k$)이다.

팁

Example

Set $A=\{0\}, B=\{0,1\}, C=\{11\}$일 때 각 Set의 Kleene closure

• Solution
  $A$의 Kleene closure는 String 0을 임의의 Finite 수 만큼 자신과 연결한 것이다.
  즉 $A^\ast=\{0^n\mid n=0,1,2,\dots\}$이다.
  $V=\{0,1\}$일 때의 $V^\ast = B^\ast$가 된다.
  $C^\ast=\{1^{2n}|n=0,1,2,\dots\}$이다.

Finite-state Automata

Output이 없는 Finite-state machine을 Finite-state automaton(복수: Automata)라고 하며 Output을 가지지 않으나 Final state set을 가진다.

Finite-state automaton $M=(S,I,f,s_0,F)$는 Finite state set $S$, Finite input alphabet $I$, Transition function $f$($f:S\times I\to S$), Initial(Start) state $s_0$, $S$의Final(Accepting) state의 Subset $F$를 가진다.

Finite-state automaton은 State table이나 State diagram으로 나타낼 수 있다.
Final state는 State diagram에서 이중 원을 사용하여 표시한다.

팁

Example

Finite-state automaton $M=(S,I,f,s_0,F)$가 $S=\{s_0,s_1,s_2,s_3\},I=\{0,1\},F=\{s_0,s3\}$이며 $f$가 아래의 표와 같을 때 State diagram\

• Solution\

Finite-state machine $M=(S,I,f,s_0,F)$의 Transition function $f$는 모든 State pair와 String에 대해 정의되도록 확장 가능하다.
즉, $f$는 $f:S\times I^\ast\to S$로 확장 가능하다.
String $x=x_1x_2\dots x_k$가 $I^\ast$에 존재할 때 $f(s_1,x)$는 State $s_1$에서 시작하여 $x$의 각 Symbol을 왼쪽에서 오른쪽으로 Input으로 사용하여 얻은 State이다.
$s_2=f(s_1,x_1), s_3=f(s_2,x_2)$이고 최종적으로 $f(s_1,x)=f(s_k,x_k)$가 된다.
이 Extended transition function $f$를 결정론적 Finite-state machine $M=(S,I,f,s_0,F)$에 대해 Recursive하게 정의할 수 있다.

1. 모든 State $s\in S$에 대해 $f(s,\lambda)=s$
2. 모든 $s\in S, x\in I^\ast, a\in I$에 대해 $f(s,xa)=f(f(s,x),a)$

Structural induction과 이 Recursive Definition을 사용하여 Extended transition function의 Property를 증명할 수 있다.

Language Recognition by Finite-State Machines

String $x$가 Machine $M=(S,I,f,s_0,F)$에 의해 Reconized(Accepted)일 때 Initial state $s_0$에서 Final state $f(s_0, x)$가 $F$에 존재하는 State이다.
Machine $M$에 의해 Language recognized(Language accepted) 되는 것을 Notation $L(M)$으로 표현하며 $M$에 의해 Recognized인 모든 String의 Set이다.
두 Finite-state automaton이 Equivalent라고 할 때는 동일한 Language가 Reconize일 때를 의미한다.

팁

Example

위 그림의 Automaton $M_1, M_2, M_3$의 Language recognized

• Solution
  $M_1$의 Final state는 $s_0$뿐이다.
  $s_0$에서 $s_0$로의 String은 0개 이상의연속된 1로 구성된 String이다.
  즉, $L(M_1)=\{1^n\mid n=0,1,2,\dots\}$이다.
  $M_2$의 Final state는 $s_2$뿐이므로 $s_0$에서 $s_2$로의 String은 1, 01 뿐이다.
  즉, $L(M_2)=\{1, 01\}$이다.
  $M_3$의 Final state는 $s_0, s_3$이다.
  $s_0$에서 $s_0$로의 String은 0개 이상의 연속된 0로 구성된 String, $s_0$에서 $s_3$로의 String은 0개 이상의 0으로 구성된 String 뒤 10 이후임의의 String이 오는 것이다.
  즉 $L(M_3)=\{0^n, 0^n10x\mid n=0,1,2,\dots , \text{and }x \text{ is any string}\}$이다.

팁

Example

아래 특정 Finite-state automaton 구축
$(a)$. 두 개의 0으로 시작하는 Bit string set
$(b)$. 두 개의 연속된 0을 포함하는 Bit string set
$(c)$. 두 개의 연속된 0을 포함하지 않는 Bit string set
$(d)$. 두 개 이상의 연속된 0으로 끝나는 Bit string set
$(e)$. 최소 두 개의 0을 포함하는 Bit string set

• Solution
  $(a)$의 경우 아래 그림과 같다.
  
  두 개의 0으로 시작하지 않는 이상 Final state가 될 수 없게 Finite-state automaton을 구축한다.
  $(b)$의 경우 아래의 그림과 같다.
  
  앞 전 두 개의 연속된 0이 나오지 않는 이상 Final state가 될 수 없게 Finite-state automaton을 구축한다.
  $(c)$의 경우 아래의 그림과 같다.
  
  두 개의 연속된 0이 나오는 경우 Final state가 될 수 없게 Finite-state automaton을 구축한다.
  $(d)$의 경우 아래의 그림과 같다.
  
  두 개 이상의 연속된 0이 나오지 않는 경우 Final state가 될 수 없게 Finite-state automaton을 구축한다.
  $(e)$의 경우 아래의 그림과 같다.
  
  최소 두 개의 0을 포함하여야 Final state가 될 수 있게 Finite-state automaton을 구축한다.

팁

Example

아래 두 Finite-state automaton이 Equivalent인 지 확인\

• Solution
  String $x$가 $M_0$에 의해 Recognized되기 위해 $s_0$에서 $s_1, s_4$로의 String이 되어야 한다.
  $s_0$에서 $s_1$은 1만이 $x$가 될 수 있다.
  $s_0$에서 $s_4$는 1개 이상의 0과 마지막이 단일 1로 이루어진 String이 되어야 한다.
  위 사항을 $M_1$에 의해 Recognized되는 지 확인해보아야 한다.
  String $x$가 $M_1$에 의해 Recognized되기 위해 $s_0$에서 $s_1$으로의 String이 되어야하는데 0개 이상의 0과 단 하나의 1로 구성된 String이 $x$가 될 수 있고, 위 조건과 동일하기에 두 Finite-state automaton은 Equivalent이다.

바로 위 예시처럼 Equivalent finite-state automaton들의($M_1$이 $M_0$)에서 가능한 최소 State를 가진 Finite-state automaton으로 구성하는 Procedure를 Machine minimization이라고 한다.

Nondeterministic Finite-State Automata

앞전 다뤘던 Finite-state automaton들은 Deterministic이다.
각 State와 Input value pair에 대한 Transition function에 의해 결정되는 고유한 다음 State가 존재하였기 때문이다.

Nondeterministic finite-state automaton $M=(S,I,f,s_0, F)$는 State set $S$, Input alphabet $I$, Transition function $f$($f:S\times I\to P(S)$), Starting state $s_0$, $S$의 Subset $F$(Final state로 구성)으로 구성되어 있다.

팁

Example

Nondeterministic finite-state automaton의 State table이 아래와 같을 때 State diagram(Final state: $s_2, s_3$)\

• Solution\

팁

Example

Nondeterministic finite-state automaon의 State diagram이 아래와 같을 때 State table와 Language recognized\

• Solution
  
  위 Table은 해당하는 State table이다.
  $s_0$에서 $s_0, s_4$로의 String $x$는 $s_0$에서 $s_0$으로, 즉 0개 이상의 0으로 이루어진 String이거나, $s_0$에서 $s_4$로 즉 11($s_0\to s_1\to s_4$), 01($s_0\to s_2\to s_4$)로 끝나는 String이다.
  정리하여 $L(M)=\{0^n, 0^n01, 0^n11 \mid n\geq 0\}$이다.

정보

Theorem

Language $L$이 Nondeterministic finite-state automaton $M_0$에 의해 Recognized일 때 $L$은 Deterministic finite-state automaton $M_1$에 의해서도 Recognized이다.

팁

Example

위 Nondeterministic finite-state automaton과 똑같은 Language를 Recognize하는 Deterministic finite-state

• Solution
  
  위 Nondeterministic automaton과 동일한 Deterministic finite-state automaton이다.
  이 Deterministic automaton의 State는 Nondeterministic automaton의 모든 State set의 Subset이다.
  Input symbol에 대한 Subset의 다음 State는 이 Subset의 모든 Element의 Nondeterministic automaton의 다음 State를 포함하는 Subset이다.
  $\{s_0\}$은 0의 Input으로 $s_0, s_2$로 Transition되기에 $\{s_0,s_2\}$로, 또 $\{s_0\}$가 1의 Input으로 $\{s_1\}$, $\{s_2\}$가 1의 Input으로 $s_4$로 가기에 $\{s_0,s_2\}$는 $\{s_1, s_4\}$로 이동하게 된다.
  동일한 방법으로 $\{s_1,s_4\}$는 0의 Input으로 $\{s_3\}$으로 이동하고, 1의 Input으로 $\{s_3,s_4\}$로 이동한다.
  $\{s_3, s_4\}$에서 0이나 1의 Input으로 $s_3$으로 밖에 이동할 수 없기에 위와 같은 구조가 된다.
  위 Deterministic finite-state automaton의 Initial state는 $\{s_0\}$이며 Final state set은 $s_0, s_4$를 포함한 모든 Set이 된다.

12.4. Language Recognition

Set $I$에 대한 Regular expression은 아래와 같이 Recursive하게 정의된다.
Symbol $\empty$는 Regular expression이다.(Empty set)
Symbol $\lambda$는 Regular expression이다.(Empty string)
Symbol $x$는 $x\in I$일 때 Regular expression이다.
Symbol $(AB), (A\cup B), A^\ast$는 $A, B$가 Regular expression일 때 Regular expression이다.($(AB)$= $A, B$의 Concatenation, $A^\ast$= $A$의 Kleene closure)

Regular expression으로 표현하는 Set을 Regular set이라고 한다.

팁

Example

Regular expression $10^\ast, (10)^\ast, 0\cup 01, 0(0\cup 1)^\ast, (0^\ast 1)^\ast$의 Regular set의 String

• Solution
  $10^\ast$는 1 뒤에 0이 0개 이상 존재하는 String, $(10)^\ast$는 10이 0개 이상 존재하는 String, $0\cup 01$은 0이나 01, $0(0\cup 1)^\ast$는 0으로 시작하는 모든 String, $(0^\ast1)^\ast$sms 0으로 끝나지 않는 String이다.

Kleene's Theorem

정보

Theorem

Kleene's Theorem

모든 Regular set이 Finite-state automaton들에 의해 Recognized된다.

• Proof
  Regular set은 Regular expression에 의해 정의되며, 이는 재귀적이다.
  모든 Regular set이 Finite-state automaton에 의해 Recognize됨을 증명하기 위해 아래와 같은 작업을 수행할 수 있다.
  1. $\empty$이 Finite-state automaton에 의해 Recognized
  2. $\{\lambda\}$가 Finite-state automaton에 의해 Recognized
  3. $\{a\}$가 $I$의 Symbol일 때 Finite-state automaton에 의해 Recognized
  4. $AB$가 $A,B$ 모두 Recognized일 때 Finite-state automaton에 의해 Recognized
  5. $A\cup B$가 $A,B$ 모두 Recognized일 때 Finite-state automaton에 의해 Recognized
  6. $A^\ast$가 $A$가 Recognized일 때 Finite-state automaton에 의해 Recognized
  $\empty$는 Nondeterministic finite-state automaton에 의해 Recognized되므로 증명할 수 있다.
  
  $\{\lambda\}$의 경우 Initial state $s_0$을 생성한 이후 Transition 시키지 않으며 증명 할 수 있다.
  
  $\{a\}$의 경우 Initial state $s_0$과 Final state $s_1$을 생성한 후 Input이 $a$ 일 때 Transition시켜 증명할 수 있다.
  
  $AB, A\cup B$의 경우 $M_{A}=(S_A,I,f_A,s_A,F_A), M_B=(S_B,I,f_B,s_B,F_B)$가 Recognized된다고 가정할 때 $M_{AB}=(S_{AB},I,f_{AB},s_{AB},F_{AB})$를 구성하여 $A$의 String은 $M_A$의 Initial state $s_A$에서 $B$의 String인 $s_B$로 Transition될 수 있어야하며 $B$의 String은 Combined machine의 Final state로 Transition되어야 한다. 결과적으로 아래와 같이 생성하여 증명할 수 있다.
  
  같은방식으로 $M_{A\cup B}=(S_{A\cup B}, I,f_{A\cup B},s_{A\cup B}, F_{A\cup B})$를 구성하여 $M_A,M_B$를 병렬로 연결하여 아래와 같이 생성하여 증명할 수 있다.
  
  $A^\ast$의 경우 $M_{A^\ast}=(S_{A^\ast},I,f_{A^\ast}, s_{A^\ast},F_{A^\ast})$를 구성하여 $s_{A^\ast}$는 모든 $S_A$를 포함하고, $F_{A^\ast}$는 모든 $F_A$와 $s_{A^\ast}$를 포함한다($\lambda$가 Recognized이기에).
  정리하여 그림으로 아래와 같이 생성하여 증명할 수 있다.\

팁

Example

Nondeterministic finite-state automaton을 구성하여 Regular set $1^\ast \cup 01$을 Recognize

• Solution
  먼저 $1^\ast$를 Recognize하는 Machine을 구축한다.
  즉 $M_{A^\ast}$로 나타낼 수 있다.
  01에 대한 Machine은 $1^\ast$를 $A^\ast$로 나타내었기에 $M_{AB}$로 나타낼 수 있다.\

Regular Sets and Regular Grammers

정보

Theorem

Regular set은 Regular grammer로 생성된 set만이 가능하다.

• Proof
  $G=(V,T,S,P)$가 Set $L(G)$를 생성하는 Regular grammer일 때 $L(G)$가 Regular임을 보이기 위해 $L(G)$를 Recognize하는 Nondeterministic finite-state machine $M=(S,I,f,s_0,F)$를 구성한다.
  State set $S$에는 $G$의 Nonterminal symbol $A$마다 하나의 State $s_A, s_F$가 포함된다.
  Start state $s_0$는 Start symbol $S$로부터 형성된 State이다.
  $M$의 Transition은 $A\to a$가 Production이라면 Input $a$에 대해 $s_A$에서 $s_F$로의 Transition이 포함되며, $A\to aB$가 Production이라면 Input $a$에 대해 $s_A$에서 $s_B$로의 Transition이 포함된다.
  Final state set $s_F$가 포함되고 $G$에서 $S\to A$가 Production인 경우 $s_0$도 포함된다.
  $M$이 Recognize하는 Language가 Grammer $G$에 의해 생성되는 Language와 같다($L(M)=L(G)$)
  따라서 Regular grammer로 생성한 Set은 Regular set이다.
  Regular set을 생성한 Grammer는 Regular grammer임을 보이기 위해 $M$이 이 Set을 Recognize하는 Finite-state machine이며 $M$의 Inital state $s_0$이 Transition의 다음 State가 아닌 경우를 가정하여 Grammer $G=(V,T,S,P)$는 $G$의 Symbol set $V$, Terminal symbol set $T$, State set $S$, $G$의 Production set $P$일 때 Start symbol $S$는 Start state $s_0$에서 형성한 Symbol이다.
  $G$의 Production set $P$는 $M$의 Transition으로부터 형성된다.
  State $s$가 Input $a$에 따라 State $t$로 이동한다면 Production $A_s\to aA_t$가 $P$에 포함되며 $A_s$는 State $s$로부터 형성된 Nonterminal symbol이다.
  Production $S\to \lambda$는 오직 $\lambda \in L(M)$일 때만 $P$에 포함된다.
  $G$의 Production이 $M$의 Transition에 해당하고 Terminal로 이어지는 Production이 Final state로의 Transition에 해당하기에 $L(G)=L(M)$이다.

팁

Example

아래 그림의 Finite-state automaton이 Recognize하는 Regular set 생성\

• Solution
  Grammer $G=(V,T,S,P)$는 이 Automaton이 Recognize하는 Set을 생성하며 $V=\{S,A,B,0,1\}$, $S,A,B$는 $s_0,s_1,s_2$, $T=\{0,1\}$, $S$는 Start symbol, Production $P$는 $S\to 0A, S\to 1B, S\to 1, S\to \lambda, A\to 0A, A\to 1B, A\to 1, B\to 0A, B\to 1B, B\to 1$이다.

A Set Not Reognized by a Finite-State Automaton

특정 Set이 Regular가 아님을 보여줄 수 있다.

팁

Example

$\{0^n1^n\mid n=0,1,2,\dots\}$가 Regular가 아님을 증명

• Solution
  위 Set을 Regular라고 가정하고 이를 Recognize하는 Nondeterministic finite-state automaton $M=(S,I,f,s_0,F)$가 존재하여야 한다.
  이 Machine의 State 수를 $N$이라고 하면($N=|S|$) $M$은 0의 개수와 1의 개수가 같은 모든 String을 Recognized해야 하므로 $M$은 $0^n1^n$을 Recognized한다.
  State sequnce $s_0,s_1,\dots,s_{2N}$은 $s_0$에서 시작하여 $0^n1^n$을 Input으로 사용하여 얻어진다.
  $s_1=f(s_0,0),s_2=f(s_1,0),\dots, s_N=f(s_{N-1},0),s_{N+1}=f(s_N, 1),\dots, s_{2N}=f(s_{2N-1},1)$가 된다($s_{2N}$이 Final state).
  State가 $N$개 뿐이므로 Pigeonhole principle에 따라 처음 $N+1$개의 State 중 적어도 두 개는 동일해야 한다.
  즉, $0\leq i\leq j\leq N$을 만족하는 $s_i,s_j$가 $t=j-i$일 때 $f(s_i,0^t)=s_j$가 만족한다는 의미이다.
  Input 0을 $t$번 사용하여 $s_j$에서 $s_j$로 돌아오는 Loop가 존재한다는 뜻이 된다.
  Input string $0^N0^t1^N=0^{N+t}1^N$은 성립할 수 없으므로 $M$에 의해 Recognize될 수 없다.
  위 Contradiction으로 $\{0^n1^n\mid n=0,1,2,\dots\}$는 Regular가 아님을 알 수 있다.\

More Powerful Types of Machines

Finite-state automaton은 Memory 제한으로 인해 많은 Computation을 수행할 수 없다.
Finite-state automaton의 한계때문에 더 편리한 Computation model을 사용하는데 그 중 하나는 Pushdown automaton이다.

Pushdown automaton은 모든 Finite-state automaton의 기능을 포함하고 무제한 Memory를 제공하는 Stack을 포함한다.
Stack의 Top에 Symbol을 놓거나 Symbol을 제거할 수 있다.
Pushdown automaton은 Input으로 사용될 때 Empty stack을 생성하는 모든 String으로 구성된 경우 Set을 Recognize하거나 Set이 Input으로 사용될 때 Final state로 이어지는 모든 String으로 구성된 경우 Set을 Recognized한다.
Pushdown automaton은 Context-free grammer에 의해 생성된 Language인 경우에만 Set을 Recognize한다는 것을 보여줄 수 있다.

Context-free grammer에 의해 생성된 Language로 표현할 수 없는 Set도 존재하는데 그 중 하나가 $\{0^n1^n2^n\mid n=0,1,2\}$이다.
앞 Set은 Pushdown automaton에 의해 Recognized될 수 없는 이유로는 0의 수 만큼 1의 수를 일치하는 지 살릴 때 Stack이 비워지게 되어 2에 해당하는 개수를 살릴 수 없다.

Pushdown automaton보다 더 강력한 Linear bounded automaton이라는 Machine이 존재하는데 이는 앞 Set을 인식할 수 있다.
Linear bounded automaton은 Context-sensitive language를 Recognized할 수 있다.
하지만 Linear bounded automaton의 경우 Phrase-structure grammer에 의해 생성된 모든 Language를 Recognized할 수 없다.

특수 Type machine의 한계를 피하기 위해 Turing machine이라는 것이 존재한다.
Turing machine은 Finite-state machine의 모든 기능과 양쪽 방향으로 무한한 Tape를 포함하고 그 Tape를 읽고 쓸 수 있으며 Tape의 앞, 뒤로 이동 가능하다.

12.5. Turing Machines

Definition of Turing Machines

Turing machine $T=(S,I,f,s_0)$는 Finite-state set $S$, Blank symbole $B$를 포함하는 Alphabet $I$, $S\times I$에서 $S\times I\times \{R,L\}$의 Partial function $f$, Starting state $s_0$로 구성된다.
Partial function은 Domain에 있는 Element에 대해서만 정의한다(일부 (state, symbol) pair에 대한 Partial function $f$가 정의되지 않을 수 있지만 정의된 Pari에 대해서는 고유한 (state, symbol, derection) 존재).
Turing machine 정의의 Partial function에 해당하는 five-tuples coressponding을 Transition rule이라고 한다.

위 그림은 Turing machine에 대해서 나타내고 있다.
Turing machine의 Tap는 주어진 순간에 Finite인 Nonblank symbol을 가지고 있다.
Turing machine의 각 Step에서의 동작은 현재 State와 Tape symbol에 대한 Partial function $f$의 Value에 따라 달라진다.
각 Step에서 현재 Tape symbol $x$를 읽고 만약 Control unit이 State $s$이고 Partial function $f$가 $(s,x)$ Pair에서 정의되어 있으며 $f(s, x)=(s',x',d)$인 경우 Control unit은 아래의 작업을 수행한다.

1. State $s'$로 들어간다.
2. 현재 Cell에 Sumbol $x'$를 쓰고 $x$를 지운다.
3. Direction $d=R$일 경우 오른쪽, $d=L$일 경우 왼쪽 Cell로 이동한다.

위 Step을 $(s,x,s',x',d)$ Form의 Five-tuple로 표기한다.
만약 Pari $(s,x)$에 대해 Partial function $f$가 정의되어 있지 않다면 Turing machine $T$는 중지한다.

Turing machine 작동 시작 시 Inital state $s_0$에 존재하며 Tape의 가장 왼쪽 비어있지 않은 Symbol 위에 위치한다.
만약 Tape가 모두 비어 있다면, Control head는 임의의 Cell에 위치할 수 있다.
Control head를 가장 왼쪽에 비어있지 않은 Tape symbol 위에 배치하는 것을 Machine의 Inital position이라고 한다.

팁

Example

Turing machine $T$가 일곱 개의 Five-tuple로 정의될 때 이 Machine이 아래 그림에 나타난 Tape에서 실행될 때의 Final tape

$(s_0,0,s_0,0,R),(s_0,1,s_1,1,R),(s_0,B,s_3,B,R),(s_1,0,s_0,0,R),(s_1,1,s_2,0,L),(s_1,B,s_3,B,R),\\(s_2,1,s_3,0,R)$

• Solution
  $T$는 State $s_0$에서 시작하며 Tape의 가장 왼쪽 비어있지 않은 Symbol 위에 위치한다.
  첫 Step에서 $(s_0,0,s_0,0,R)$을 사용하여 가장 왼쪽 비어있지 않은 Cell에서 0을 읽고, State $s_0$를 유지하며 이 Cell에 0을 쓰고 Cell 오른쪽으로 이동한다.
  위 행동을 반복하여 동작시킨 그림은 아래와 같다.
  
  마지막 Step에서 State $(s_3, 0)$으로 시작하는 Five tuple이 없기에 중지한다.

Using Turing Machines to Recognize Sets

Set $V$를 Alphabet $I$의 Subset이라고 할 때 Turing machine $T=(S,I,f,s_0)$는 String $x$가 $V^\ast$에 속할 때 $T$가 $x$가 Tape에 쓰여진 Initial position에서 시작하여 Final state에서 멈출 때만 $x$를 Recognize한다고 한다.
$T$가 $V^\ast$의 Subset $A$를 Recognize한다고 할 때 $x$가 $T$에 의해 Recognized되기에 $x$가 $A$에 속해야 한다.

팁

Example

두 번째 Bit로 1을 가지는 Bit string set을 인식하는 Turing machine

• Solution
  Regular set은 $(0\cup 1)1(0\cup 1)^\ast$이다.
  Turing machine이 왼쪽에서 가장 왼쪽의 비어 있지 않은 Tape cell에서 시작하여 오른쪽으로 이동하며 두 번째 Symbol이 1인 지 확인하는 것이기에 두 번째 Symbol이 1이면 Machine은 Final state로 이동해야 하며 그렇지 않다면 Machine은 중지하지 않거나 Nonfinal state에서 중지해야 한다.
  Machine을 구성하기 위해 $(s_0,0,s_1,0,R), (s_0,1,s_1,1,R)$을 포함하여 첫 번째 Symbol을 읽고 Turing machine을 State $s_1$으로 이동하고 0이면 State $s_2$, 1이면 State $s_3$로 이동하도록 $(s_1,0,s_2,0,R), (s_1,1,s_3,1,R)$을 포함한다.
  두 번째 Bit가 0인 String은 Recognize하지 않기에 $s_2$는 Nonfinal state, $s_3$는 Final state여야 한다.
  $(s_2,0,s_2,0,R)$을 포함하여야 한다.
  Blank나 1 bit string을 Recognize 않기 위해 $(s_0,B,s_2,0,R), (s_1, B, s_2, 0, R)$을 포함한다.
  나열 된 일곱 개의 5-tuple로 구성된 Turing machine $T$는 Bit string이 두 개 이상의 Bit를 가지고 있고 Input string의 두 번째 Bit가 1일 때만 Final state $s_3$로 종료된다.
  Bit string이 두 개 미만이거나 두 번째 Bit가 1이 아니면 Machine은 Non final state $s_2$에서 종료된다.

팁

Example

$\{0^n1^n\mid n\geq 1\}$ Set을 Recognize하는 Turing machine

• Solution
  Machine을 구축하기 위해 Marker로 사용할 Sub tape symbol $M$을 사용하여 $V=\{0,1\}, I=\{0,1,M\}$로 두고 $V^\ast$의 String의 Subset을 Recognize 할 것이다.
  Turing machine은 가장 왼쪽에 있는 0을 $M$으로 바꾸고 String의 가장 오른쪽에 있는 1을 $M$으로 바꾸며 앞뒤로 이동하며, String이 0의 Block 뒤에 동일한 수의 1의 Block으로 구성되어 있을 때만 Final state $s_6$를 가지고 종료한다.
  Marker $M$을 사용하여 이미 검사한 가장 왼쪽과 오른쪽 Symbol을 추적한다.
  $(s_0,0,s_1,M,R),(s_0,0,s_1,0,R),(s_1,1,s_1,1,R),(s_1,M,s_2,M,L),(s_1,B,s_2,B,L),\\(s_2,1,s_3,M,L),(s_3,1,s_3,1,L),(s_3,0,s_4,0,L),(s_3,M,s_5,M,R),(s_4,0,s_4,0,L),\\(s_4,M,s_0,M,R),(s_5,M,s_6,M,R)$이다.
  예시로 String $000111$은 Machine이 작동하는 동안 $M00111, M0011M, MM011M, MM01MM, MMM1MM, MMMMMM$ 순서로 변경된다.

Computing Functions with Turing Machines

Turing machine은 간단히 요약하여 Partial function의 값을 찾는 것이다.
Turing machine $T$가 Input으로 String $x$를 받았을 때 Tape에 String $y$를 남기고 정지한다고 할 때 $T(x)=y$로도 표현 가능하다.
$T$의 Domain은 $T$가 정지하는 String set이며 $T$가 $x$를 Input으로 받았을 때 정지하지 않을 경우 $T(x)$는 정의되지 않는다.

Non-negative integer의 $k$-tuple에서 Non-negative integer set으로의 Function으로서 Turing machine을 고려하기 위해 Tape에 Integer의 $k$-tuple을 표현할 방법으로 Unary representation을 사용한다.
Non-negative integer $n$은 $n+1$개의 1로 이루어진 String으로 표현한다(0, 5 = 1, 111111).
$k$-tuple($n_1,n_2,\dots,n_k$)를 표현하기 위해 각 수+1에 해당하는 1과 구분자 $\ast$로 나타낸다.
(4-tuple (2, 0, 1, 3) = $111\ast 1\ast 11\ast 1111$)

팁

Example

Non-negative integer를 더하는 Turing machine 구성

• Solution
  Function $f(n_1,n_2)=n_1+n_2$를 계산하는 Turing machine $T$를 만들기 위해 Pair $(n_1,n_2)$는 $n_1+1$개의 1과 $\ast$, $n_2+1$개의 1로 이루어진 String으로 표현된다.
  Machine $T$는 Input으로 앞 String을 받아 $n_1+n_2+1$개의 1로 이루어진 Tape를 출력한다.
  Machine $T$는 Input string의 가장 왼쪽 1에서 시작하여 1을 지우는 Step을 수행하며 $n_1$이 0일 경우 $\ast$ 앞에 더 이상 1이 없으므로 정지하고, $\ast$를 가장 왼쪽에 남아있는 1로 교체한 후 정지한다.
  즉 $(s_0,1,s_1,B,R),(s_1,\ast,s_3,B,R),(s_1,1,s_2,B,R),(s_2,1,s_2,1,R),\\(s_2,\ast,s+3,1,R)$
  의 5-tuple 을 사용할 수 있다.

Different Types of Turing Machines

Turing machine의 Capability를 확장할 수 있다.
예시로 각 Step에서 Turing machine이 오른쪽이나 왼쪽으로 이동하거나 이동하지 않을 수 있도록 허용하거나 여러 Tape에서 작동하도록 허용하거나, $n$개의 Tape를 사용할 때 $(2+3n)$-tuple로 Turing machine을 설명할 수 있다.
Turing machine의 Tape를 2차원으로 허용할 수 있으며 이 경우 좌우뿐만 아니라 상하로도 이동할 수 있다.
여러 개의 Tape head가 서로 다른 Cell을 동시에 읽도록 허용할 수 있다.
Turing machine이 Nondeterministic을 허용하여 (State, Tape symbol) Pair가 Turing machine의 5-tuple 중 두개 이상의 첫 번째 Element로 나타날 수 있다.

Turing machine의 Capability를 제한할 수도 있다.
Tape가 한 차원에서만 무한하도록 제한하거나 Tape alphabet을 두 개의 Symbol로만 제한할 수도 있다.

Turing machine은 특정 Turing machine과 그 Input의 Incoding을 제공받았을 때 모든 Turing machine의 계산을 시뮬레이션할 수 있는 단일 Turing machine을 구성하는 것이 가능하며 이를 Universal turing machine이라고 한다.

The Church-Turing Thesis

어떤 문제에 대해 Turing machine이 해결할 수 있다는 것을 명시하는 것을 Church-turing thesis 라고 한다.
Theorem이 아닌 Thesis로 불리는 이유로는 유효한 Algorithm에 의한 해결 가능성 개념이 비공식적이고, 부정확한 반면, Turing machine에 의한 해결 가능성 개념은 공식적이고 정확하기 때문이다.

Computational Complexity, Computability, and Decidability

Turing machine을 사용하여 가장 쉽게 연구할 수 있는 문제는 "yes"나 "no"로 답할 수 있는 Decision problem이다.

Decision problem는 특정 Class의 Proposition이 True인 지 여부를 묻는 Problem이다.

앞에서 다뤘던 Halting problem은 주어진 Input string $x$에 대해 Turing machine $T$가 정지하는 지 묻는 Decision problem이다.

정보

Theorem

Helting problem은 Unsolvable decision problem이다.
즉, Turing machine $T$와 Input string $x$의 Incoding이 주어졌을 때 $T$가 $x$가 Tape에 쓰여졌을 때 정지하는 지 판단할 수 있는 Turing machine은 존재하지 않는다.

팁

Example of Unsolvable decision problems

• 두 개의 Context-free grammer가 동일한 String set을 생성하는 지 결정
• 주어진 Tile set이 겹치지 않게 반복 허용하여 전체 평면을 덮을 수 있는지 결정
• Hilbert's Tenth Problem
  Integer coefficient를 가진 Polynomial equation에 대한 Integer solution이 존재하는 지 결정

Turing machine으로 계산할 수 있는 Function을 Computable function, 불가능한 Function을 Uncomputable function이라고 한다.

앞에서 다뤘던 P, NP라고 불리는 Problem class에 대해서도 Turing machine의 개념을 사용하여 정확히 정의할 수 있다.
Deterministic turing machine $T=(S,I,f,s_0)$에서 Transition rule은 $S\times I$에서 $S\times I\times \{R,L\}$로의 Partial function $f$에 의해 정의된다.
Machine의 Transition rule은 5-tuple $(s,x,s',x',d)$ 형태로 표현되며(s, s': State, x, x': Tape symbol, d: Direction), 같은 Pair (s,x)로 시작하는 두 개의 Transition rule은 존재하지 않는다.

Nondeterministic turing machine은 Partial function이 아닌 5-tuple로 구성된 Relation을 사용하여 정의된다.
같은 Pair (s,x)로 시작하는 두 개의 Transition rule이 존재할 수 없는 제한이 사라진다.
즉, 각 (State, Tape symbol) Pair로 시작하는 Transition rule이 여러 개 존재할 수 있다.
따라서 Nondeterministic turing machine은 현재 State와 읽고 있는 Tape symbol의 일부 Pair에 대해 Transition choice가 존재한다.
Nondeterministic turing machine의 작동 각 Step에서 Machine은 현재 State와 Tape symbol Pair로 시작하는 Transition rule 중 하나를 선택한다.
선택할 때 마다 Step을 "Guess"하는 것으로 간주할 수 있다.
Deterministic turing machine과 마찬가지로, Nondeterministic turing machine은 현재 State와 Tape symbol로 시작하는 Transition rule이 정의되지 않았을 때 중지된다.
Nondeterministic turing machine $T$가 주어졌을 때, String $x$가 $T$에 의해 인식된다고 말하는 것은 $T$의 Transition sequence가 Final state로 끝나는 경우 Machine이 $x$가 Tape에 적혀 있는 Inital position에서 시작할 때만 가능하다.
Nondeterministic turing machine $T$가 주어질 때 String $x$가 $T$에 의해 Recognized된다고 말하는 것은 $T$의 Transition sequence가 Final state로 끝나는 경우 Machine이 $x$가 Tape에 적혀 있는 Initial position에서 시작할 때만 가능하다.
Nondeterministic turing machine $T$는 $x$가 $T$로 Recognized set $A$에 $x\in A$이다.

Decision problem은 Input의 크기에 따라 Polynomial time 안에 Deterministic turing machine에 의해 Solvable이라면 Class P이다.
즉, Decision problem은 특정한 Decision problem을 해결하는 Deterministic turing machine $T$와 모든 Integer $n$에 대해 $T$가 $n$ 길이의 String이 입력되었을 때 $p(n)$인 Polynomial이 존재한다면 P에 속한다.

Decision problem이 Class NP에 속하는 것은 Nondeterministic turing machine에 의해 Input 크기에 따라 Polynomial time 안에 해결할 수 있을 때이다.
즉, Decision problem은 문제를 해결하는 Nondeterministic problem $T$와 모든 Integer $n$에 대해 $T$가 $n$ 길이의 String이 입력되었을 때 Polynomial $p(n)$가 존재한다면 NP에 속한다.

모든 Deterministic turing machine은 각 (State, Tape symbol) Pair가 Machine을 정의하는 단 하나의 Transition rule 내에서 발생하는 Nondeterministic turing machine으로 간주될 수 있으므로 $P\subseteq NP$이다.