Theory of computation (2)

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

DFA(Deterministic Finite Automaton)
1. notation $$M(Q, \Sigma, \delta, q_0, F)$$

• $Q$ : State들의 집합
• $\Sigma$ : input alphabet
• $\delta$ : $Q \times \Sigma \to Q$ transition function
• $q_0$ : $q_0 \in Q$ initial state (1개)
• $F$ : $F \in Q$ Final states (1개 이상 가능)

2. example

notation으로 이해하기 어려우므로 DFA 한가지 예제로 이해를 해봅시다.

$$M(\{a,b,c,d\}, \{0,1\}, \delta, a, \{d\})$$ $$\delta(a,0)=b, \text{ } \delta(a,1)=a$$ $$\delta(b,0)=b, \text{ } \delta(b,1)=c$$ $$\delta(c,0)=d, \text{ } \delta(c,1)=a$$ $$\delta(d,0)=d, \text{ } \delta(d,1)=d$$

위의 DFA 에는 state가 $a,b,c,d$ 4개가 있습니다.

$0,1$ symbols 로 이우러진 alphabet $\{0,1\}$이 있습니다.

transition function의 갯수는 state의 갯수(4) X alphabet의 길이(2) 가 됩니다.

initial state는 $a$ 입니다.

final state는 $d$ 입니다.

이해를 쉽게 하기 위해 그래프로 나타내면 다음과 같습니다.

그래프에서 보는 바와 같이 symbol들은 edge로 표현되고, state는 node로 표현됩니다. 또한 initial state $a$는 아무런 symbol표시 없는 화살표가 하나 붙게 되고, final state $d$는 2중 동그라미로 나타냅니다.

DFA에서 initial state $a$에서 출발해서 final state $d$로 state가 바뀌게 되는 string은 accept하게 됩니다.

예를 들면 111은 $aaa$가 됩니다. 그럼 마지막 state가 final state $d$ 가 아니므로 111 string은 accept하지 않습니다.

1010은 state가 $aabcd$ 가 되므로 final state $d$로 끝나게 되므로 1010 string은 accept 하게 됩니다.

graph를 table 형식으로 나타내면 다음과 같습니다.

		0	1
	a	b	a
	b	b	c
	c	d	a
	d	d	d

$\delta$ notation의 확장

$\delta ^* (a, 10)=b$

위의 식은 state $a$ 에서 edge 1로 이동하고 거기서 다시 edge 0으로 간 state가 $b$ 라는 의미입니다.

$\delta ^* (a, 10)=\delta (\delta(a,1), 0)=b$ 로 표현될수 있습니다.

DFA에서 accept 되는 string의 집합 notation $$L(M)=\{w \in \Sigma^* ; \delta ^* (q_0, w) \in F\}$$

위 식은 $q_0$ initial state에서 출발해서 final state에 도달하는 transition function을 적용해서 나온 모든 string의 집합을 의미합니다. 즉 위 조건을 만족하는 string은 accept 된 string이라고 보면 됩니다.