Introduction to Theory of Computation 2장_6 정리/설명

Introduction to Theory of Computation 2장_6 정리/설명

<Closure under the regular operations>
      - Retular Operation의 폐쇄성 -

Theorem 2.6.1 Union 연산에 대한 폐쇄성
 같은 알파벳 ∑에 대한 A1과 A2가 regular language라면 A1∪A2도 regular language이다.

 (설명) 위쪽의 네모 박스를 M1, 아래쪽의 네모 박스를 M2라고 두고, 각각의 M1, M2가 합집합 연산을 하기 위해서는 q0라는 start state에서 ε을 입력받아서 M1, M2 양쪽으로 갈 수 있는 NFA M을 만든다.
    (※ ε 심벌을 통해서 입력값에 영향을 받지 않도록 한다.)


Theorem 2.6.2 Concatenation 연산에 대한 폐쇄성
 같은 알파벳 ∑에 대한 A1과 A2가 regular language라면 A1A2도 regular language이다.

 (설명) 왼쪽의 네모 박스를 M1, 오른쪽의 네모 박스를 M2라고 두고, 각각의 M1, M2가 연결(concatenation) 연산을 하기 위해서는  M1에서 끝나는 accept state들에서 M2의 start state로 ε로 연결되는 NFA M을 만든다.
    (※ ε 심볼을 통해서 입력값에 영향을 받지 않도록 한다.)

**주의 : M1에서 끝나던 accept state들을 M2의 start state와 연결될 때 일반 state들로 바꿔줌.  


Theorem 2.6.3 Star 연산에 대한 폐쇄성
 A가 regular language라면 A*도 regular language이다.  
       // star operation이란? A* = {w₁, w₂ ... w | n≥0, w₁, w₂ ... ∈A}  -> 0번 이상의 루프를 의미.

 (설명) NFA N이 0번의 심볼을 입력하여도 accept 돼야 하므로 start state를 accept 상태로 만들어야 한다. 또한, N 내부에 있던 accept state들도 루프를 돌아 accept/reject를 판단하기 때문에 ε를 통해 start state들과 연결한다.