유한 오토마타

유한 오토마타(영어로 finite state machine 또는 finite automaton)는 아주 단순한 컴퓨터의 계산 모델이다. 몇 개의 상태와 몇 개의 전이로 이루어지며, 주어진 문자열을 수락하거나 거부한다.

예

먼저 상태 전이도를 이용해 유한 오토마타를 비형식적으로 설명해 보자.

오토마타는 상태로 이루어져 있는데, 그림에는 둥근 상태 q₀, q₁, q₂가 3개 있다. 이 상태들 사이에 있는 화살표가 전이이다. 오토마타에는 시작 상태도 있어야 하는데, 여기서는 상태 q₀이다. 시작 상태는 흔히 어떤 상태에서도 나오지 않는 화살표가 들어가는 모습으로 나타낸다. 또 오토마타에는 보통 수락 상태가 있으며, 이중선으로 그린다. 그림에서는 상태 q₂가 수락 상태이다.

이렇게 만든 오토마타는 어떤 문자열을 수락한다. 오토마타에 문자열을 넣으면 오토마타는 그 문자열을 수락해 보려고 한다. 수락하면 ‘예’, 수락하지 않으면 ‘아니요’라고 답한다. 이 오토마타는 글자 “a, b, c”로 이루어진 문자열을 수락해 보므로, 문자열 “abbc”를 넣어 보자.

시작 상태 q₀에서 출발하고 입력은 문자열 “abbc”이다. 이제 화살표를 따라간다.

문자열은 보통 왼쪽에서 오른쪽으로 읽으므로 먼저 기호 “a”를 읽는다. 입력 “a”에 대한 화살표는 상태 q₁로 가므로 그 상태로 옮기고 문자열에서 기호 “a”를 지운다. 이제 입력은 문자열 “bbc”이다.

입력 “b”에 대한 화살표는 다시 노드 q₁로 돌아온다. 다시 첫 글자를 지우면 입력은 문자열 “bc”가 된다. 이번에도 상태 q₁에 머문다. 마지막으로 입력은 문자열 “c”이다. 상태 q₁에서 입력 “c”에 대한 화살표를 따라 상태 q₂로 간다.

입력 문자열의 글자를 모두 읽었고, 수락 상태인 상태 q₂에 있다. 따라서 이 유한 오토마타는 문자열 “abbc”를 수락한다.

마지막에 수락 상태에 있지 않았다면 오토마타는 문자열을 수락하지 않는다. 어떤 상태에서 더 갈 곳이 없을 때도 마찬가지로 문자열을 수락하지 않는다. 예를 들어 입력 “ab”는 상태 q₁에 도착한 뒤 거기서 끝나므로 오토마타는 이 문자열을 수락하지 않는다. 문자열 “aabbc”도 수락되지 않는다. 상태 q₁에서 글자 “a”에 대한 화살표가 없기 때문이다.

이처럼 유한 오토마타는 어떤 문자열의 집합을 인식하는 데 쓰인다. 실제로는 예를 들어 주어진 입력 문자열이 올바른 이메일 주소인지 판별하는 데 오토마타를 쓸 수 있다.

유한 오토마타의 정의

오토마타를 제대로 다루려면 지금까지 직관적으로 설명한 유한 오토마타를 형식화해야 한다.

(결정적) 유한 오토마타는 5-튜플 ⟨Q, Σ, δ, q₀, F⟩이다. 여기서

• Q는 상태의 유한집합,
• Σ(대문자 시그마)는 알파벳(기호나 글자의 유한집합),
• δ: Q × Σ ⟶ Q는 전이 함수,
• q₀ ∈ Q는 시작 상태,
• F ⊆ Q는 수락 상태의 집합이다.

앞의 오토마타로 돌아가 보자.

상태의 집합 Q에는 상태가 3개 있으므로 Q = {q₀, q₁, q₂}이다. 알파벳 Σ에는 오토마타가 수락하거나 거부할 문자열을 만드는 글자가 들어 있다. 여기서는 아마 알파벳 Σ= {a, b, c}이겠지만, 이를 포함하는 임의의 집합이어도 된다. 시작 상태 q₀은 그대로 상태 q₀이다. 이 오토마타에서 수락 상태의 집합에는 상태가 하나뿐이므로 F = {q₂}이다.

전이 함수는 글자가 붙은 세 화살표를 뜻한다. 기호 δ: Q × Σ ⟶ Q는 δ가 두 인자, 즉 Q의 상태와 Σ의 글자를 받는 함수(사상이라고 하는 편이 더 정확하다)라는 뜻일 뿐이다. 함수를 호출하면 새 상태를 돌려준다. 이 전이 함수를 표로 정의하면 다음과 같다.

$$\begin{array}{ccc}Q& \mathrm{\Sigma }& \to Q\\ q_0& a& q_1\\ q_1& b& q_1\\ q_1& c& q_2\end{array}$$

따라서 δ(q₁, c)를 호출하면 세 번째 행이 적용되어 함수는 상태 q₂를 돌려준다. 상태 전이도와 같은 결과이다. 상태 q₁에서 입력이 글자 “c”이면 상태 q₂로 간다. 오토마타가 문자열을 수락한다는 것을 형식적으로 정의하기 전에, 이 개념을 직관적으로 이해한 상태에서 다른 예를 몇 가지 살펴보자.

다른 예

1. 이진 알파벳, 즉 Σ= {0, 1} 위에서 동작하며 1로 끝나는 문자열만 수락하는 오토마타를 만드시오. 예를 들어 문자열 1, 01, 000001, 0101011을 수락한다.

   

   이 오토마타에는 시작 상태 q₀과 수락 상태 q₁의 두 상태가 있다. 입력이 숫자 1이면 언제나 수락 상태 q₁로 가서 그 상태에 머문다. 반대로 입력이 숫자 0이면 비수락 상태 q₀으로 가서 역시 그 상태에 머문다.

2. 이진 알파벳 위에서 첫 글자와 마지막 글자가 다른 문자열만 수락하는 오토마타를 만드시오.

   

   이 오토마타는 첫 단계에서 바로 두 “부분 오토마타”로 갈라진다. 문자열이 0으로 시작하면 왼쪽 부분으로 들어가 계속 그곳에 머물고, 1로 시작하면 오른쪽 부분으로 옮긴다. 그다음은 늘 하던 대로이다. 왼쪽 부분에 있을 때 입력이 1이면 수락 상태로 가서 그 상태에 머문다. 입력이 0이면 수락 상태가 아닌 상태 q₁로 간다.

   앞의 오토마타들과 달리 이 오토마타에는 수락 상태가 여러 개 있다. 즉 F = {q₃, q₄}이다.

3. 이진 알파벳 위에서 0이 두 번 연달아 나오지 않는 문자열만 수락하는 오토마타를 만드시오.

   

   이 오토마타는 두 가지 점에서 흥미롭다. 첫째, 빈 문자열을 수락한다. 오토마타에 빈 문자열을 넣으면 시작 상태가 수락 상태이기도 할 때 오토마타는 빈 문자열을 수락하는데, 이 오토마타가 그런 경우이다. 빈 문자열에는 0이 두 번 연달아 나오지 않으므로 이것이 맞는 결과이다. 둘째, 이 오토마타는 모든 상태가 수락 상태이다. 오토마타가 문자열을 수락하지 않는 경우는 상태에서 나가는 전이가 없을 때뿐이다. 이런 일은 상태 q₁에서 일어난다. 이 상태에는 0에 대한 전이가 없는데, 그런 전이가 있으면 문자열에 0이 두 번 연달아 나오기 때문이다.

4. 알파벳 {-,+,.,0,1,…,9} 위에서 수를 나타내는 문자열만 수락하는 오토마타를 만드시오. 즉 2, 548, 98263 같은 정수와 5584.48, 3.14 같은 소수를 수락하고, 둘 다 빼기 기호가 붙은 음수 -2, -548, -3.14와 더하기 기호를 명시한 +2, +548, +3.14도 수락해야 한다. 또 수 0.123을 앞의 0 없이 .123으로 쓸 수 있어야 하고, 두 부호를 붙인 경우도 마찬가지이다. 숫자 10개에 대한 전이 10개를 일일이 쓰는 대신 기호 N을 쓰기로 한다.

   

5. 이진 알파벳 위에서 0ⁿ1ⁿ 꼴의 문자열만 수락하는 오토마타를 만드시오. 즉 문자열의 앞에 0이 몇 개 있고 그 뒤에 같은 개수의 1이 오는 문자열이다. 이런 문자열의 예로 0011, 00001111, 01이 있다.

   이런 오토마타는 만들 수 없다. 0의 개수를 어디에도 “기억”할 수 없기 때문이다. 두 번째 예처럼 “부분 오토마타”를 여러 개 만들어야 하는데, n의 값마다 하나씩 필요하므로 “부분 오토마타”가 무한히 많아야 한다.

오토마타의 계산의 형식화

유한 오토마타 자체는 이미 형식적으로 정의했다. 이제 이 오토마타가 실제로 무엇을 하는지, 즉 오토마타의 계산을 정의해야 한다.

오토마타의 형상: 순서쌍 ⟨q, w⟩ ∈ Q × Σ^∗를 오토마타의 형상이라고 한다. 여기서 q는 오토마타가 지금 있는 상태이고 w는 문자열에서 아직 읽지 않은 부분이다. Σ^∗는 알파벳 Σ의 클레이니 폐포, 즉 알파벳 Σ의 글자로 만들 수 있는 모든 문자열의 집합이다. 이 폐포에는 빈 문자열도 들어 있으며, 빈 문자열은 ε으로 나타낸다.

오토마타 ⟨Q, Σ, δ, q₀, F⟩로 문자열 w를 수락해 보려고 할 때, 오토마타는 시작 형상 ⟨q₀, w⟩에 있다. 다음 오토마타로 돌아가서

문자열 w = abbc를 수락해 보려고 하면 시작 형상은 ⟨q₀, abbc⟩이다.

계산 단계는 집합 (Q × Σ^∗) × (Q × Σ^∗) 위의 관계 ↦, 즉 오토마타의 형상 사이의 관계로 정의한다. w = w₀w₁… w_n이 문자열 w에서 아직 읽지 않은 부분이라고 하자. δ(q₁, w₀) = q₂일 때, 그리고 그때에만 두 순서쌍 ⟨q₁, w₀w₁… w_n⟩과 ⟨q₂, w₁… w_n⟩이 관계 ↦에 있다고 하고 다음과 같이 쓴다.

$$⟨q_1,w_0{w}_1\dots w_n⟩\mapsto ⟨q_2,w_1\dots w_n⟩,$$

앞의 예로 돌아가면 시작 형상은 ⟨q₀, abbc⟩이다. 상태 전이도에서 입력 “a”에 대해 상태 q₁로 옮길 수 있음을 알 수 있다. δ(q₀, a) = q₁이므로 다음과 같이 쓸 수 있다.

$$⟨q_0,abbc⟩\mapsto ⟨q_1,bbc⟩,$$

이것으로 계산을 한 단계 진행했다. 주어진 입력(= 아직 읽지 않은 부분의 첫 글자)에 대해 어느 상태로 가야 하는지 보고, 그 상태로 옮긴 다음 아직 읽지 않은 부분에서 첫 글자를 지웠다. 그 결과 새 형상을 얻었다.

계산 단계 관계의 반사적·추이적 폐포는 ↦ ^∗로 나타낸다. 오토마타의 형상 K₁, K₂에 대하여 K₁ ↦ ^∗ K₂라고 쓰면, 형상 K₁에서 계산 단계 몇 개를 거쳐 형상 K₂에 도달할 수 있다는 뜻이다. 다시 말해 다음과 같은 형상의 유한한 수열이 존재한다.

$$K_1\mapsto K_{11}\mapsto K_{12}\mapsto K_{13}\mapsto \cdots \mapsto K_2$$

예를 들어 이 오토마타에서는 ⟨q₀, abbc⟩ ↦ ^∗ ⟨q₁,bc⟩가 성립한다. 계산을 두 단계 진행하면 문자열 “bc”가 남고 상태 q₁에 있기 때문이다. 즉 다음과 같은 형상의 수열이 존재한다.

$$⟨q_0,abbc⟩\mapsto ⟨q_1,bbc⟩\mapsto ⟨q_1,bc⟩$$

오토마타가 문자열 w를 수락한다는 것은 다음을 만족하는 q_f ∈ F가 존재하는 것과 동치이다. $$⟨q_0,w⟩{\mapsto }^{\ast }⟨q_f,\epsilon ⟩$$ 즉 계산 단계의 어떤 수열이 있어서, 그 수열의 끝에서 문자열 전체를 읽었고 오토마타의 수락 상태에 있을 때, 그리고 그때에만 오토마타는 문자열 w를 수락한다. 문자열 전체를 읽었다는 것은 형상에서 문자열 자리에 빈 문자열 ε이 있다는 것으로 나타난다. 이 오토마타는 문자열 abbc를 수락한다. 다음과 같은 형상의 수열이 존재하고

$$⟨q_0,abbc⟩\mapsto ⟨q_1,bbc⟩\mapsto ⟨q_1,bc⟩\mapsto ⟨q_1,c⟩\mapsto ⟨q_2,\epsilon ⟩$$

상태 q₂가 수락 상태, 즉 q₂ ∈ F이기 때문이다.

오토마타가 인식하는 언어는 오토마타가 수락하는 모든 문자열의 집합이다. 오토마타 A의 언어는 L(A)로 나타낸다. 따라서 L(A) ⊆ Σ^∗이고 다음이 성립한다.

$$L(A)=\{w\in {\mathrm{\Sigma }}^{\ast }|A\text{가 수락하는 문자열 }w\}$$

정규 언어는 어떤 유한 오토마타가 인식하는 언어이다.

두 유한 오토마타가 동치라는 것은 두 오토마타가 같은 언어를 인식한다는 뜻이다. 즉 L(A₁) = L(A₂)가 성립하면 오토마타 A₁과 A₂는 동치이다.

참고 자료

• M. Sipser: Introduction to the Theory of Computation
• Aho, Sethi, Ullman: Compilers: Principles, Techniques, and Tools