[계산이론](4)[nondeterministic]

다음은 º을 증명할 차례지만...
이걸 증명하기 위해선 nondeterministic(비결정성)을 알아야 한다.

 

nondeterministic

이전의 오토마타는 어디로 상태가 변화할 지 명확하지만,
nondeterministic은 다음 상태가 여러개이므로, 다음 상태가 뭔지 정확하지 않다.
따라서 모든 경우의 수를 판단하며 따라간다.

 

DFA: Deterministic Finite Automata
    오직 1개의 transition
NFA: Nondeterministic Finite Automata
     0, 1, 다수의 transition을 가질 수 있음
     ε을 transition으로 가질 수 있다

NFA의 계산

• 여러 경우의 수가 있다면 평행세계마냥 나눠진다
• 만약 해당 symbol의 transition이 없다면 그 경우의 수는 죽는다(die)
• ε는 symbol을 다음으로 이동하지 않고 다음 상태로 간다
• 모든 경우에서 적어도 하나의 오토마타가 accept하면 그 NFA는 그 string을 accept한다
  예) 다음 NFA N이 주어질 때 w=101을 accept하는지 판단하시오
  
  주어진 NFA의 일부 경우만 보자면,
  q1 -> q2-> die (10)
  q1 -> q2 -> q3 -> q3 -> q3 (1ε01)
  따라서 accept하는 경우가 있으니 w∈L(N)이다.

 

NFA의 정규 표현식

정의 ($Q$, $\sum$, $\delta$, $q_0$, $F$)

• states ($Q$)
  상태의 유한 집합
• alphabet ($\sum$)
  행동에 쓰이는 문자의 유한 집합
• transition funtion ($\delta : Q \times \sum_\epsilon \rightarrow P(Q)$)
  transition에 ε도 들어가므로, $\sum_ε=\sum\cup{ε}$인 $\sum_ε$을 정의한다.
  여러 transition을 표현하기 위해 Q의 멱집합(power set)으로 공역을 정의한다.
• start state ($q_0 \in Q$)
  상태 중 1개
• accept state ($F ⊆ Q$)
  상태의 부분 집합

 

NFA의 accept 정의

accept의 정의
M = ($Q$, $\sum$, $\delta$, $q_0$, $F$)이고
string w = w1 w2 w3 ... wn이라 할 때
상태의 sequence를 (r0, r1, r2, ..., rn)이라 하면
단, r ∈ $\sum_\epsilon$
다음 세 조건을 만족하면 accept라고 한다.

• $r_0 = q_0$
• $r_{r+1}$ ∈ $\delta(r_i, w_{i+1})$ {단, i = 0, ... , n-1}
• $r_n \in F$
  예) 다음 NFA N이 주어질 때 w=110을 accept하는지 수학적으로 판단하시오
  
  

1. r0 = q0 = q1
2. i
   i=0: $\delta(r_0, w_1) = \delta(q_1, 1) = {q_2}$
   i=1: $\delta(r_1, w_2)$
       $\delta(q_2, 1) = \{q_1, q_3\}$
       $\delta(q_2, \epsilon) = \{q_3\}$
       $= \{q_1, q_3\}$ ∋ r2
   i=2: $\delta(r_2, w_3)$
       $\delta(q_1, 0) = \{q_1\}$
       $\delta(q_3, 0) = \{q_3\}$
       $= \{q_1, q_3\}$ ∋ r3
3. r3중 하나인 q3 $\in$ F 이므로,
   따라서 $w \in L(M)$ (M accepts w)