Introduction to Theory of Computation 2장_4,5 용어/개념정리

Introduction to Theory of Computation 2장_4,5 용어/개념 정리

< NFA >
   : Nondeterministic Finite Automata.

NFA Diagram

여태 보았던 DFA Diagram과 다른 점 세 가지가 있을 것이다. 
   1. q₁으로 가는 옵션이 0과 1 두 가지가 있다.
   2. q₂에서 q₃로 가는 symbol 중에서 λ(empty string)가 보인다.
   3. q₃에서 symbol 0을 읽지 못한다.

    (※ λ란?  empty string, 길이가 0인 문자열   // 공집합과는 다름. )


 위의 State Digram에서 010110을 Input 한 다음의 트리 구조를 봐보자. 
   **이제부터 q₁, q₂, q₃, q₄를 1,2,3,4로 쉽게 나타낼 것임.

  >> accept string은 '11', '101'이다.
   빨간색 동그라미가 쳐진 state ④로 가기 위해 "필수적인 input string"들은 '1ε1'과 '101'이다. 따라서 ε는 읽지 않아도 되는 empty string이기 때문에 결과적으로 accept string은 '11', '101'이다.

 원래 주어진 NFA의 각 단계마다 도달 가능한 state끼리 묶어 위의 그림을 DFA로 표현해보자.

 ∴결과적으로 NFA는 DFA와 "동작 과정"이 다를 뿐 reject, accept 하는 결과는 똑같다.


< DFA와 NFA의 차이 >
: NFA는 위에서 보았듯이 트리 구조가 나타나며, DFA에 비해 조건이 완화되어 사용하기 편리하다.
      (오직 하나의 길만 존재하는 DFA에 비해 "NFA는 기능이 추가되었다"라고도 말할 수 있다.)


(예제) M = (Q, ∑,  δ, q, F)에서, { w ∈ {0,1}* | w has a 1 in the 3rd position from the right }이다.
                                                                      // 오른쪽에서 세 번째 오는 글자가 1인 string.

 앞전 글에서 이야기했던 DFA를 예로 들어 설명해보자.

DFA Diagram

위의 사진은 DFA diagram이다. (관련 설명은 앞전 글에 작성되어있음.)

NFA Diagram

  이것은 동일한 문제의 NFA diagram이다.
왜 오른쪽에서 세번째 글자가 1인 string이 accept 될 수 있는가?
 1. 뒤에서 첫 번째 올 수 있는 string이 0 or 1
 2. 뒤에서 두 번째 올 수 있는 string이 0 or 1
 3. 뒤에서 세 번째 올 수 있는 string이 1           => 이 과정을 따라 accept 된다..

사진에서 보이다시피 DFA와 NFA의 차이를 한눈에 볼 수 있는데 다른 state로 가기 위한 길이 하나만 존재해야 하는 DFA에 비해서 NFA는 DFA의 조건이 완화되어 적용되기 때문에 사용하기에 편리하다는 특성을 이해할 수 있을 것이다.


----------------------------------------------------------------------------------------------------------------------------------------------------


< NFA 정의 >
 Definition 2.4.1. A NFA is a 5-tuple M=(Q', Σ, δ, q', F')
   - Q'  :  a set of state.          // Q' = P(Q) 
                                              // NFA의 Q'의 부분집합들을 DFA의 P(Q)로 정의한다.
   - ∑  :  a set of symbols.
   - δ  :  transition function.       // ∑e = ∑ ∪ {ǫ}
                                                   // δ : P(Q) x ∑e → Q'
   - q  :  start state.
   - F  :  a set of accept state.       // F' = { R⊆Q' | F∩R ≠ ∮ }
                                                     // accept state들이 Q의 부분집합들(P(Q))와 겹치는 게 하나라도 있어야 함.


 (예제) NFA에서 N=(Q, Σ, δ, q, F) 일 때,

위의 그림과 같은 diagram을 가진다. δ에 의해 생기는 테이블을 작성하라.

Q={1,2,3,4}, ∑={1,2}, q={1}, F={4}이다.  

δ	0	1	λ
1	{1}	{1,2}	∮
2	{3}	∮	{3}
3	∮	{4}	∮
4	{4}	{4}	∮

(예제) NFA N=(Q, Σ, δ, q, F)에서 Q={1,2,3}, Σ={a,b}, q=1, F={2}일 때, δ이 가진 테이블이 다음과 같다.

N의 diagram을 그리시오.

------------------------------------------------------아래 사진들 DFA로 변환 과정-------------------------------------------

DFA M=(Q', Σ, δ', q', F') 에서 각각의 state들을 구하고, 구한 state를 통해서 diagram으로 변환한다.

 

 

하지만 이때, 시작 state {1,2}에서 갈 수 없는 state들을 삭제할 수 있다.
따라서 {1}, {3}, {2}, {1,3} state들이 표현할 필요가 없어진다.

 

결과적으로 아래와 같은 간단한 DFA로 표현을 할 수 있다.