Theory of computation (6)

본 내용은 KOCW 한양대학교 “오토마타 및 계산이론” 강좌 7강을 보며 정리한 내용입니다.

GTG(Generalized Transition Graph)

GTG는 NFA를 포함하는 개념입니다.

GTG는 NFA의 Transition에 symbol 이 아닌 regular expression 이 들어간 Graph 를 애기합니다.

complete GTG 는 모든 state에서 다른 state로의 Transition 이 모두 있는것입니다. 혹 Transition 이 일어나지 않는 state간에는 공집합 $\phi$로 지정해줍니다.

위의 그래프에서 Transition symbol이 아닌 regular expression이라고 한다면 위 그래프는 GTG 입니다.

위의 Graph 에서 accept 되는 language를 regular expression 으로 표현하면 다음과 같습니다.

$$r_{ii}^* r_{ij} (r_{jj} + r_{ji} r_{ii}^* r_{ij})^*$$

initial state $q_0$ 에서 final state $q_f$ 로 Transition 하는 방법은 두가지가 있습니다.

먼저 $q_i \to q_j$ 로 Transition 하는 방법

$$r_{ii}^* r_{ij} r_{jj}^ {* }$$

그리고 $q_0 \to q_f \to q_0 \to q_f$ 로 Transition 하는 방법

$$r_{ii}^* r_{ij} r_{ji}r_{ii}^* r_{ij}$$

state가 3개인 경우에도 위 공식을 적용할수 있습니다. initial state 와 final state 를 제외한 state를 지워주면 가능합니다. 예제를 통해 알아보겠습니다.

위 그래프에서 initial state와 final state가 아닌 $q_k$를 지워주면서 $q_k$를 통해 발생할수 있는 Transition 을 모두 반영해주는 graph로 변형해주면 됩니다.

$q_i$에서 자기 자신 $q_i$ 로 Transition 하는 방법은 2가지 입니다. 첫번째는

$$r_{ii}$$

이고, 또 다른 방법은 $q_i \to q_k \to q_i$로 가는 방법입니다.

$$r_{ik} r_{kk}^* r_{ki}$$

따라서 최종 $q_i$ 에서 자기 자신으로의 Transition 은

$$r_{ii} + r_{ik} r_{kk}^* r_{ki}$$

---

마찬가지로 $q_j$에서 자기 자신 $q_j$ 로 Transition 하는 방법도 2가지 입니다.

첫번째는

$$r_{jj}$$

이고, 또 다른 방법은 $q_j \to q_k \to q_j$ 로 가는 방법입니다.

$$r_{jk} r_{kk}^* r_{kj}$$

따라서 최종 $q_j$ 에서 자기 자신으로의 Transition 은

$$r_{jj} + r_{jk} r_{kk}^* r_{kj}$$

---

이제 $q_i$ 에서 $q_j$로 Transition 하는 방법에 대해 알아보겠습니다.

첫번째는 $q_i \to q_j$로 Transition 하는 방법입니다.

$$r_{ij}$$

두번째는

$q_i \to q_k \to q_j$로 Transition 하는 방법입니다.

$$r_{ik} r_{kk}^* r_{kj}$$

입니다.

최종적으로 두개를 합친 regular expression 으로 나타내면

$$r_{ij} + r_{ik} r_{kk}^* r_{kj}$$

입니다.

---

마지막으로 $q_j$ 에서 $q_i$로 Transition 하는 방법에 대해 알아보겠습니다.

첫번째는 $q_j \to q_i$로 Transition 하는 방법입니다.

$$r_{ji}$$

두번째는

$q_j \to q_k \to q_i$로 Transition 하는 방법입니다.

$$r_{jk} r_{kk}^* r_{ki}$$

입니다.

최종적으로 두개를 합친 regular expression 으로 나타내면

$$r_{ji} + r_{jk} r_{kk}^* r_{ki}$$

입니다.

간단히 표로 정리해보면 다음과 같습니다.

Transition 방향은 모두 행에서 열로 가는걸로 생각하면 됩니다.

	$q_i$	$q_j$
$q_i$	$r_{ii} + r_{ik} r_{kk}^* r_{ki}$	$r_{ij} + r_{ik} r_{kk}^* r_{kj}$
$q_j$	$r_{ji} + r_{jk} r_{kk}^* r_{ki}$	$r_{jj} + r_{jk} r_{kk}^* r_{kj}$