오토마타와 형식언어 01 DFA(결정적 유한 오토마타)

DFA(Deterministic Finite Accepter)

DFA Deterministic이므로 transition function에 따라 고정적으로 다음 state로 전이된다. 또한 Accepter이므로 yes or no를 출력한다.
\[M = (Q,\Sigma, \delta, q_0, F)\]
순서대로 internal states, input alphabet, transition function, initial state, final states를 의미한다.
\[\delta = Q \times \Sigma\]
다음의 예시를 보도록 하겠다.
\[M = (\{q_0,q_1,q_2\},\{0,1\}, \delta, q_0, \{q_1\})\] \[\delta(q_0,0)=q_0,\delta(q_0,1)=q_1\] \[\delta(q_1,0)=q_0,\delta(q_1,1)=q_2\] \[\delta(q_2,0)=q_2,\delta(q_2,1)=q_1\]
이러한 상황에서 101를 입력하게되면 전이 함수를 따라 이동하여 $q_0->q_1->q_0->q_1$
final state에 도달하게 되고, Accepted. 하지만 100을 입력하게되면 $q_0->q_1->q_0->q_0$
final state에 도달하지 못하여 Rejected.
Extended Transition Function
\[\delta^*=Q \times \Sigma^*->Q\]
이것은 그냥 전이 함수에 state와 symbol이 아닌 state와 string을 넣어서 간단하게 표현하는 것이다.
다음과 같은 전이 함수가 있다면 Extended transition function은 다음과 같이 계산된다.
\[\delta(q_0,a)=q_1,\delta(q_1,b)=q_2\] \[\delta^*(q_0,ab)=\delta(\delta^*(q_0,a),b)=\delta(q_1,b)=q_2\]
Language DFA에 의해 Accept되는 모든 String의 집합이다.
\[L(M)=\{w\in\Sigma^*:\delta^*(q_0,w)\in F\}\]
즉, 전이 함수를 따라 계속 다음 state로 진행하였을 때 최종적으로 final states에 도달하게 하는 모든 string을 원소로 갖는 집합이 Language이다.
Complement는 다음과 같다.
\[\overline{L(M)}=\{w\in\Sigma^*:\delta^*(q_0,w)\notin F\}\]
Trap State : 어떠한 문자를 입력해도 그 state에서 벗어날 수 없는 state를 말한다.
Regular Languages
어떠한 Launguage에 대하여 $L=L(M)$을 만족하는 DFA가 존재한다면 그것을 regular라고 한다.