[계산이론](6)[NFA를 이용한 닫힘 증명]

우리는 앞에서 NFA <-> DFA 임을 보였으며,
NFA가 recognize하는 language는 DFA로도 표현될 수 있으므로 regular language를 알 수 있다.
-> 따라서 regular language에 닫힘의 증명에서 NFA를 쓸 수 있다!

 

각자 NFA N1, N2가 있을 때 다음을 나타내는 새로운 NFA N이 정의될 수 있다면 그건 regular language에 닫혀있는 것이다!

 

Union의 증명 (2트)

NFA N1, N2의 accept하는 것을 모두 포함해야 하므로,
그냥 머신 2개 동시에 돌리면 됨 (NFA의 분기를 이용~)

 

N1 = ($Q_1$, $\sum_1$, $\delta_1$, $q_1$, $F_1$), N2 = ($Q_2$, $\sum_2$, $\delta_2$, $q_2$, $F_2$)이 있을 때,
N = ($Q$, $\sum$, $\delta$, $q$, $F$) 이라고 정의하자.

• $Q = {q0} \cup Q_1 \cup Q_2$
• $\sum = \sum_1\cup\sum_2$
• $q = q_0$
• $F=F_1\cup F_2$
  그리고 δ를 정의하면
• δ(q, a)
  q ∈ Q1 : δ1(q, a)
  q ∈ Q2 : δ2(q, a)
  q = q0 ∧ a = ε : {q1, q2}
  q = q0 ∧ a ≠ ε : ∅
  즉, N1 ∪ N2는 이런 형태이다
  
  

 

Concatnation의 증명

DFA로만 증명해야 했을 땐, 붙은 문자열의 어느 부분을 잘라서 M에 넣을지 고민이었지만, NFA는 모든 경우의 수를 다 봐서 ㄱㅊ

N1 = ($Q_1$, $\sum_1$, $\delta_1$, $q_1$, $F_1$), N2 = ($Q_2$, $\sum_2$, $\delta_2$, $q_2$, $F_2$)이 있을 때,
N = ($Q$, $\sum$, $\delta$, $q_0$, $F$) 이라고 정의하자.

• $Q = Q_1 \cup Q_2$
• $\sum = \sum_1\cup\sum_2$
• $q_0 = q_1$
• $F=F_2$
  그리고 δ를 정의하면
• δ(q, a)
  q ∈ Q1 ∧ q ∉ F1 : δ1(q, a)
  q ∈ F1 ∧ a ≠ ε : δ1(q, a)
  q ∈ F1 ∧ a = ε : δ1(q, a) ∪ {q2}
  q ∈ Q2 : δ2(q, a)
  즉, N1 º N2는 이런 형태이다

N1 -> N2일때 모든 경우의 수 ( δ1(q, a) ∪ {q2} )봄

 

Star의 증명

N1 = ($Q_1$, $\sum_1$, $\delta_1$, $q_1$, $F_1$)이 있을 때,
N = ($Q$, $\sum$, $\delta$, $q$, $F$) 이라고 정의하자.

• $Q = {q_0} \cup Q_1$
• $\sum = \sum_1$
• $q = q_0$
• $F={q_0} \cup F_1$
  그리고 δ를 정의하면
• δ(q, a)
  q ∈ Q1 ∧ q ∉ F1 : δ1(q, a)
  q ∈ F1 ∧ a ≠ ε : δ1(q, a)
  q ∈ F1 ∧ a = ε : δ1(q, a) ∪ {q1}
  q = q0 ∧ a = ε : {q1}
  q = q0 ∧ a ≠ ε : ∅
  즉, N1*는 이런 형태이다