오토마타와 형식언어: 유한 오토마타 (Finite Automata) (3)

이어서 유한 오토마타(3)이다. 조금만 더 있으면 DFA(Deterministic Finite Accepter)에 이어 NFA(Non-determininstic Finite Accepter)에 대해서도 배우게 된다.

우선 중간 정리가 조금 필요하다.

중간 정리:

1. DFA는 다음 5개의 원소로 이루어져 있다: M =(Q, Σ,δ,q0,F)
2. DFA는 전이 그래프(Transition Graph)로 표현하면 더 직관적으로 이해가 편리하다.
3. 모든 qi,qj ∈ Q 와 w ∈ Σ∗ 에 대해, δ∗(qi,w)=qj 임과 G(M)에 label w를 갖는 qi~qj까지의 보행이 존재함은 동치이다.

Example 하나를 풀어보도록 하자.

위와 같은 dfa가 구성이 되어있다고 할 때, string w = abba 가 input 으로 들어오면 승인이 되는가? (Final State가 되는가?)

δ∗를 이용해서 문제를 풀면 된다.

우선 문제는 다음과 같은 식으로 표현이 가능하다:

δ∗(q0,abba)=?

즉, Initial State 인 q0에서 abba 라는 string w 가 input 으로 들어왔을 때, final state가 q2 인지 확인하라는 것이다. 다시 말해, string w 를 accept하는지, reject하는지 하나씩 input 해 보면서 확인해 보면 된다.

하나씩 해보자.

우선은 아래가 첫 번째 단계이다.

δ∗(δ(q0,a),bba)

Initial State (q0)에서 abba라는 string이 들어왔을 때 왼쪽에서 오른쪽 (-->) 으로 "하나씩" 읽기 때문에 a부터 검사해 보는 것이다. 즉, state가 q0 일 때 a가 들어오면 다음 state (Q) 가 무엇인지 풀면 된다.

δ∗(δ(q0,a),bba) = δ∗(q0,bba) 가 된다. q0인 상태에서 a 가 input으로 들어오면 dfa에서 보는 것처럼 q0 그대로에 머무르게 된다. 그럼 순차적으로 다음 input들도 처리해보자.

δ∗(δ(q0,b),ba) = δ∗(q1,ba)
δ∗(δ(q1,b),aa) = δ∗(q2, a)
δ∗(δ(q2,a),λ) = δ∗(q2, λ) = q2

λ(람다)를 만남으로써 string w의 식 풀이는 끝나게 된다. 최종 state는 q2가 되며, 위 dfa그림에서는 q2에 double circle이 그려져 있으므로 q2가 final state인 것을 확인할 수 있다. 즉, abba 의 값을 가지고 있는 string w 는 위 dfa에 의해 최종적으로 승인(accept)된다.

다음 문제로 넘어가자.

위와 같은 dfa가 있다고 가정했을 때, 위 dfa를 Language로 표현하면?

L(M)=L((a+ba)bb((a+b))

일단은 위와 같은 식으로 Language 표현이 가능하다고는 하는데, 솔직히 아직은 왜 이렇게 나오는지 잘 모르겠다. Chapter 5 정도부터 이걸 자세히 다룬다고 하는데, 일단은 두고 추후에 다시 설명해볼 수 있으면 하도록 하겠다.

다음 예제다.

Σ={a,b} 에 대한 string 중 ab로 시작하는 모든 string을 인식하는 dfa를 구성하여라.

우선 이 문제를 풀려면 위 아이패드 노트에서도 적어두었지만, 처음 두 symbol이 매우 중요하다. ab로 시작하는 모든 string을 인식하는 dfa이니까, 일단 가장 short route 를 생각하면 편하다.

final state로 가는 가장 짧은 루트를 그려라.

즉, string 의 길이가 얼마나 길든, ab를 일단 받으면 final state일 수 있도록 dfa를 구성하면 될 것 같다.

일단은 아래와 같다.

Initial State인 q0에서 a를 받으면 q1, 그 다음에 b를 받으면 q2로 가고, 이를 final state로 지정하면 된다. 그리고 q2이후에는 어떠한 input alphabet이 들어와도 상관없으니 a,b의 무한 루프를 만들어 승인 트랩 상태 (final trap state)로 만들어주면 된다.

그러나 q0과 q1에서 각각 a와 b가 아닌 b와 a가 들어왔을 때 전이될 수 있는 state가 필요하니 이거를 q3라는 새로운 상태를 지정함으로써 해결한다. 당연히, q3는 final state가 아니므로 double circle을 그릴 필요가 없으며, 한 번 q3로 가면 그 이후에 어떤 input alphabet이 와도 reject 당하기 때문에 비승인 트랩 상태(non-final trap state)로 그리면 된다.

이렇게 간단한 문제들을 풀어봤지만, dfa를 이해하는 데 있어 중요한 단계였던 것 같다. 아직 dfa에 대해 끝나지는 않았다. 아마 한 포스트 정도 더 게시할 것 같다.