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

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

예

알고리즘을 설명하기 전에 무엇을 하려는 것인지 예로 살펴보자. 다음 정규 표현식 a(b|c)x^∗가 있다고 하자. 이 정규 표현식이 나타내는 언어를 말로 설명하면, 글자 “a”로 시작하고 그다음에 글자 “b” 또는 “c”가 오고 그 뒤에 글자 “x”가 몇 개(0개도 가능) 이어지는 문자열의 언어이다. 이 언어를 수락하는 오토마타를 만들 수 있을까? 물론이다. 다음을 보자.

이 오토마타는 분명히 같은 언어를 수락한다. 그러면 모든 정규 표현식에 대해 그 언어를 수락하는 오토마타가 존재하느냐는 질문이 자연스럽게 떠오른다. 답은 ‘그렇다’이다.

정규 표현식을 오토마타로 바꾸는 알고리즘

입력으로 정규 표현식 R이 주어졌다고 하자. 앞의 정규 표현식 글에서 정규 표현식은 모두 여섯 가지 꼴을 가질 수 있음을 보았다. 따라서 여섯 가지 경우로 나눈다.

1. 어떤 기호 a ∈ Σ에 대하여 R = a인 경우. 즉 정규 표현식이 다루는 알파벳 Σ의 기호 하나뿐이다. 기호 a 하나를 수락하는 오토마타는 다음과 같다.

   

2. R = ϵ, 즉 빈 문자열인 경우. 빈 문자열을 수락하는 오토마타는 다음과 같다.

   

3. R = ∅, 즉 빈 언어를 나타내는 정규 표현식인 경우. 이 언어를 인식하는 오토마타는 다음과 같다.

   

4. R = R₁ ∪ R₂이고 R₁, R₂가 정규 표현식인 경우. 정규 언어의 합집합이 다시 정규 언어이고, 그 언어를 수락하는 오토마타를 만들 수 있음을 이미 알고 있다. 다시 말해 식 R₁과 R₂가 나타내는 언어를 인식하는 오토마타가 있다고 가정하고, 이 오토마타들로 식 R₁ ∪ R₂가 나타내는 언어를 수락하는 오토마타를 만든다. 예를 들어 R₁ = a이고 R₂ = ϵ이면 그 방법에 따라 다음 오토마타를 얻는다.

   

5. R = R₁ ∘ R₂이고 R₁, R₂가 정규 표현식인 경우. 앞의 경우와 같다. 정규 언어의 연접은 정규 언어이므로 그 언어를 수락하는 오토마타를 만들 수 있다. 따라서 R₁ = a, R₂ = b이면 연접은 다음과 같다.

   

6. $R=(R_1^{\ast })$이고 R₁이 정규 표현식인 경우. 이번에도 정규 언어의 클레이니 폐포가 정규 언어임을 알고 있다. 따라서 R = a^∗이면 오토마타는 다음과 같다.

   

이 규칙들을 차례로 적용하면 정규 표현식 전체를 유한 오토마타로 바꿀 수 있다.

변환 전체의 예

정규 표현식 (a|bc)^∗를 바꾸어 보자. 차례로 다음 오토마타들을 얻는다.

이렇게 얻은 오토마타는 정규 표현식 (a|bc)^∗가 나타내는 언어를 수락한다. 물론 이 오토마타는 엄청나게 복잡하고, 같은 언어를 수락하는 훨씬 간단한 오토마타가 분명히 있다. NFA를 DFA로 바꾸는 알고리즘을 쓴 다음 오토마타의 최소화를 하면 된다.

참고 자료

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