[계산이론](2)[accept의 수학적 정의]

이전에는 diagram에서 transition을 따라가며 accept를 판별하곤 했다.
이것 또한 엄밀하게 수학적으로 정의할 수 있다.

 

accept의 조건
    M = ($Q$, $\sum$, $\delta$, $q_0$, $F$)이고
    string w = w1 w2 w3 ... wn이라 할 때
    상태의 sequence를 (r0, r1, r2, ..., rn)이라 하면
    다음 세 조건을 만족하면 accept라고 한다.

• $r_0 = q_0$
• $\delta(r_i, w_{i+1}) = r_{r+1}$ {단, i = 0, ... , n-1}
• $r_n \in F$
  (즉, 시작상태 r0부터 ($Q\times\sum->Q$)를 따라가고 맨 마지막 상태 rn이 F에 포함되어야 w가 M의 language다.)

예) w = 010일떄 accept임을 증명해라

1. r0 = q0 = q1
2. i
   i=0: $\delta(r_0, w_1) = \delta(q_1, 0) = q_1 = r_1$
   i=1: $\delta(r_1, w_2) = \delta(q_1, 1) = q_2 = r_2$
   i=2: $\delta(r_2, w_3) = \delta(q_2, 0) = q_2 = r_3$
3. r3 = q2 $\in$ F
   따라서 $w \in L(M)$ (M accepts w)

이때 유한 오토마타가 나타내는 language를 regular language라고 한다.

 

참고: 형식 언어의 계층 (chomsky hierarchy)
Regular ⊂ Context-Free ⊂ Context-Sensitive ⊂ Recursively Enumerable

유한 오토마타 만들기

1. 입력 string을 보고 $\sum$을 만든다.
2. 어떤 걸 기억해야 하나 생각 후 Q를 만든다.
3. $\delta: Q\times\sum -> Q$를 만든다.
4. $q_0, F$를 각각 지정한다.

예) 101010, 01001, 11111 등의 string이 주어질 때, 1의 갯수가 짝수인 유한 오토마타를 만들어라

• 입력 string에서 $\sum$ = {0, 1}
• 1이 직전에 짝수인지 홀수인지 기억만 하면 되므로,
  Q = {$q_1, q_2$}
• $\delta = {((q_1, 0), q_1), ((q_1, 1), q_2), ((q_2, 0), q_2), ((q_2, 1), q_1)}$
• $q_0 = q_1$, $F = {q_1}$
  M = ($Q$, $\sum$, $\delta$, $q_0$, $F$)은 1의 갯수가 짝수인 string을 accept한다.
  L(M) = {w | w에서 1의 갯수가 짝수}
  주의) $\epsilon$은 accept된다. (시작하자마자 바로 a1에서 멈춤)