오토마타를 정규 표현식으로 바꾸기

임의의 유한 오토마타를 정규 표현식으로 바꾸는 방법을 알아보자.

알고리즘의 개요

입력으로 어떤 NFA A가 주어진다. 먼저 이 오토마타를 GNFA로 바꾼다. 두 번째 단계에서는 한 번에 상태를 하나씩 제거하고 전이 함수를 알맞게 고치는 일을, 시작 상태와 수락 상태의 두 상태만 남을 때까지 되풀이한다. 두 상태 사이에는 간선이 하나 있고, 그 간선에 붙은 정규 표현식이 알고리즘 전체의 결과이다. 따라서 핵심은 상태를 하나 제거한 뒤 동치인 오토마타가 되도록 오토마타를 고치는 것이다.

상태 하나 제거하기

상태 하나를 제거하는 방법은 간단한 예로 알아볼 수 있다. 오토마타의 일부가 다음과 같다고 하자.

여기서 R_i는 어떤 정규 표현식이다. 상태 q_r을 제거하면 오토마타는 어떻게 될까? 상태 q_i에 있을 때 이 구간에서 만들 수 있는 문자열이 무엇인지 생각해 보자. 상태 q_i에서 상태 q_j로 바로 가면 정규 표현식 R₄에 맞는 모든 문자열이 만들어진다.

하지만 상태 q_r로 가면 R₁ 꼴의 문자열을 만들 수 있다. 그런데 상태 q_r에서는 정규 표현식 R₂로 자기 루프를 돌 수 있으므로, 결국 $R_1\circ (R_2^{\ast })$ 꼴의 문자열을 만들 수 있다. 그리고 상태 q_r에서 상태 q_j로 갈 수 있으므로 정규 표현식 R₃을 덧붙인다. 따라서 이 경로로는 모두 $R_1\circ (R_2^{\ast })\circ R_3$ 꼴의 문자열을 얻을 수 있다.

이제 오토마타의 이 부분에서는 R₄ 꼴 또는 $R_1\circ (R_2^{\ast })\circ R_3$ 꼴의 문자열이 만들어진다는 것을 알았다. 이는 물론 정규 표현식 $(R_4)|(R_1\circ (R_2^{\ast })\circ R_3)$으로 쓸 수 있다.

이제 상태 q_r을 간단히 제거하고 두 상태 q_i와 q_j만 남긴 다음, R₄ 대신 방금 구한 정규 표현식을 적으면 된다.

이 과정을 각 상태 q_i에서 어떤 상태 q_j로 가는 모든 간선에 대해 수행한다. 자기 루프, 즉 q_i = q_j인 경우도 포함한다.

상태 하나를 제거하면 동치인 오토마타, 즉 같은 언어를 인식하는 오토마타를 얻는다.

알고리즘 전체

입력으로 NFA A = ⟨Q, Σ, δ, q₀, F⟩가 주어진다.

1. NFA A를 GNFA Z = ⟨Q′, Σ, δ′, q₀′, q_f′⟩로 바꾼다. 이제부터 Z의 상태의 개수를 문자 k로 나타낸다.
2. k = 2이면 알고리즘이 끝나고, 시작 상태와 수락 상태 사이의 간선에 결과 정규 표현식이 있다.
3. k>2이면 시작 상태와 수락 상태가 아닌 임의의 상태 q_r, 즉 q_r ≠ q₀′이고 q_r ≠ q_f′인 상태를 고른다. 그리고 다음을 만족하는 새 GNFA Z′ = ⟨Q′′, Σ, δ′′,q₀′,q_f′⟩를 만든다. $$Q^{\prime \prime }=Q^{\prime }\setminus \left\{q_r\right\}$$ 또 모든 q_i ∈ Q′′ ∖ {q_f′}과 모든 q_j ∈ Q′′ ∖ {q₀′}에 대하여 다음과 같이 정한다. $${\delta }^{\prime \prime }(q_i,q_j)=(R_4)|(R_1(R_2^{\ast })R_3),$$ 여기서 R₁ = δ′(q_i,q_r), R₂ = δ′(q_r,q_r), R₃ = δ′(q_r, q_j), R₄ = δ′(q_i, q_j)이다. 그다음 2단계로 돌아간다.

예

입력으로 다음 유한 오토마타가 주어졌다고 하자.

먼저 이 오토마타를 GNFA로 바꾼다(불필요한 ∅ 전이는 그리지 않는다).

이제 알고리즘의 두 번째 단계를 적용하여 노드를 하나 제거한다. 노드 q₂부터 시작한다. 노드 q₂를 제거하고 상태 q₁에서 상태 q_f로 가는 전이를 추가한다. 이 전이에는 b(a|b)^∗를 붙인다. 노드 q₁에서 b 꼴의 문자열로 상태 q₂에 가고, 그다음 a|b로 자기 루프를 돌아 (a|b)^∗를 얻고, 마지막으로 ε 규칙으로 q_f에 가기 때문이다. 이때 b(a|b)^∗ϵ = b(a|b)^∗이다. 다음 오토마타를 얻는다.

마지막 상태 q₁을 제거하는 일만 남았다. 상태 q_s에서 상태 q_f로 가는 간선을 추가한다. 여기에는 무엇을 붙일까? 상태 q₁에는 ε 규칙으로 가므로 이 부분은 바로 생략할 수 있다. 그다음 a로 자기 루프를 돌 수 있으므로 정규 표현식 a^∗를 얻는다. 마지막으로 간선을 따라 q_f에 가므로 이 식에 b(a|b)^∗를 연접한다. 따라서 간선에 정규 표현식 a^∗ b(a|b)^∗를 붙인다.

이제 오토마타에 상태가 두 개만 남았으므로 알고리즘이 끝난다. 간선에 붙은 것이 결과 정규 표현식이다.

참고 자료

• 예와 알고리즘 설명은 M. Sipser: Introduction to the Theory of Computation에서 가져왔다.