[계산이론](3)[regular operation]

정규 연산자 (regular operations)

이전엔 유한 오토마타와 regular language에 대해 배웠다. 이 regular language 내부에서 사용되는 연산은 다음과 같다.

regular operation

• union(∪): 집합 합치기
  A∪B = {x | x∈A or x∈B}
      예) A={a, ab}, B={x, y}
           A∪B = {a, ab, x, y}
• concatenation(º): string 합친 집합
  A º B = {xy | x∈A or x∈B}
      예) A={a, ab}, B={x, y}
            A º B = {ax, ay, abx, aby}
• star(*): concat의 연장선
  A* = {x1x2...xk | k>=0, xi∈A}
       예) A={x, y}
            A*= {ε, x, y, xx, xy, yy, xxx, ...}

-> 집합의 크기는 무한하며, A*에는 항상 ε이 포함된다.

 

regular operation은 regular language에 대해 닫혀있다!
-> 닫혀있다 = 연산을 했을 때도 항상 regular language가 나온다

 

예) 닫혀있음의 예
     정수 집합 Z가 있을 때, 뺄셈에 대해 닫혀있다.
     1-1 = 0(정수), 2-100 = -98(정수)
     그러나, 자연수 집합은 뺄셈에 대해 닫혀있지 않다.
     1-2 = -2(자연수가 아닌 정수)
-> regular language에 대해 닫혀있음을 증명하려면 연산했을 때도 regular language가 나옴을 증명해야 함
--> 연산을 한 집합을 recognize하는 유한 오토마타가 있음을 보이면 됨!!!

 

union이 닫혀있음 증명

A와 B를 recognize하는 오토마타 M1, M2가 있을 때,
A∪B를 recognize하는 오토마타 M을 만들어보자
(M1이 accept, M2가 accept할 때 M은 둘 다 accept해야 한다.)

 

단순히 M1 -> M2 이런 머신을 만든다면 문제가 발생해서 다른 방식이 필요하다.
     M1, M2 순서에 따라 못 accept되는 string 발생

M1 = ($Q_1$, $\sum_1$, $\delta_1$, $q_1$, $F_1$), M2 = ($Q_2$, $\sum_2$, $\delta_2$, $q_2$, $F_2$)이 있을 때,
M = ($Q$, $\sum$, $\delta$, $q_0$, $F$) 이라고 정의하자.
     $Q = Q_1 \times Q_2$
     $\sum = \sum_1\cup\sum_2$
     $q = (q_1, q_2)$
     $F=F_1\times F_2$
라고 정의하고 $\delta$를 정의하자.
     $\delta$는 $\delta_1, \delta_2$를 동시에 만족해야 한다.
     동시에 만족하게 하기 위해 하나의 입력을 순서대로 받는게 아니라
     pair로 받아 두 연산 모두 각각 처리해주면 된다

$\delta: Q^2\times\sum \rightarrow Q^2$ 인 $\delta$를 다음과 같이 정의한다.
$$\delta((r_1, r_2), a)=(\delta_1(r1, a), \delta_2(r_2, a))$$
이렇게 식을 세우면 임의의 regular language A, B에 대해,
A∪B를 recognize하는 finite automata를 만들 수 있다!
따라서 ∪는 regular language에서 닫혀있다!