글루시코프 작도
정의
글루시코프 작도(Glushkov construction)는 정규 표현식으로부터 ε(빈 문자열) 전이가 없는 비결정적 유한 오토마톤(NFA)을 생성하는 알고리즘이다. 이 방법에 의해 만들어진 오토마톤을 종종 글루시코프 오토마톤 또는 *위치 오토마톤(position automaton)*이라고 부른다.
역사·어원
‘글루시코프(Glushkov)’는 러시아의 컴퓨터 과학자 빅터 스테판오비치 글루시코프(Victor Stepanovich Glushkov, 1930‒1982)의 이름에서 유래한다. 그는 1961년 정규 표현식과 오토마톤 사이의 변환에 관한 연구를 발표하면서 현재 알려진 형태의 작도를 제시하였다.
구성 원리
- 정규 표현식의 각 문자(또는 기호) 위치에 고유한 번호를 부여한다.
- 각 위치에 대해 시작 집합(first set), 마지막 집합(last set), 그리고 후속 집합(follow set)을 계산한다.
- 오토마톤의 상태는 식의 위치와 초기·최종 상태로 구성되며, 전이는 후속 집합에 따라 정의된다.
- ε 전이를 사용하지 않으며, 최종 상태는 정규 표현식이 빈 문자열을 포함할 경우 추가된다.
특징 및 장점
- ε 전이 불필요: 생성된 NFA는 ε 전이가 없어 구현이 단순하고, 변환 후 바로 실행 가능하다.
- 선형 크기: 오토마톤의 상태 수는 정규 표현식에 등장하는 기호의 개수와 동일하거나 그보다 약간 많아, 일반적인 Thompson 구축에 비해 메모리 사용량이 감소한다.
- 직관적 구조: 각 상태가 정규식 내 특정 위치와 직접 대응하므로 디버깅이나 분석에 유리하다.
적용 분야
- 정규식 엔진에서 초기에 NFA를 생성한 뒤, 필요에 따라 DFA로 변환하거나 직접 시뮬레이션하는 과정.
- 컴파일러의 lexical analysis 단계에서 토큰 인식을 위한 오토마톤 생성.
- 형식 언어 이론 및 자동화 이론 연구에서 정규 표현식과 오토마톤 사이의 구조적 관계를 설명할 때.
관련 개념
- Thompson 구축: 정규 표현식에서 ε 전이를 허용하는 NFA를 만드는 다른 전통적 방법.
- 위치 오토마톤: 글루시코프 작도에 의해 생성된 오토마톤을 가리키는 용어로, 각 상태가 정규식 내 문자 위치와 일대일 대응한다.
- Determinization: 글루시코프 오토마톤을 DFA로 변환하는 과정(예: subset construction).
참고 문헌
- Glushkov, V. (1961). The abstract theory of automata. Proceedings of the 2nd International Congress on Logic, Methodology and Philosophy of Science.
- Aho, A. V., Sethi, R., & Ullman, J. D. (1986). Compilers: Principles, Techniques, and Tools (1st ed.). Addison‑Wesley. (Thompson 및 Glushkov 구축 비교)
비고
글루시코프 작도는 정규 언어 이론에서 널리 인정받는 변환 기법이며, 실제 프로그래밍 언어 및 도구에서도 구현 사례가 존재한다. 현재까지 입증된 이론적 기반이 충분히 확보되어 있다.
