글루시코프 작도

글루시코프 작도(Glushkov -)는 1960년 글루시코프가 제안한 정규 표현식에서 유한 오토마타를 얻는 작도법이다. 톰슨 작도보다 복잡하지만 $\epsilon$변환을 만들지 않는다.

글루시코프 작도는 다음 특징이 있다.

1. $\epsilon$변환이 없다.
2. 시작 상태는 내변환이 없다.
3. 각 상태의 모든 내변환은 같은 레이블을 갖는다.
4. 상태의 수는 정규 표현식의 기호 수보다 하나가 더 많다.

글루시코프 작도는 정규 표현식의 형태 유형에 따라 재귀적으로 정의된 null, first, last, follow의 4가지 함수를 반복적으로 적용하여 얻는다. 글루시코프 작도는 $\epsilon$없는 비결정적 유한 오토마타를 만들지만, 특정 정규 표현식에 대해서는 결정적 유한 오토마타를 만들 수도 있다.

쉬운 작도법

1. 정규 표현식의 각 리터럴에 상태를 부여한다.
2. 시작 상태를 추가한다.
3. 각 상태를 해당 리터럴을 소비한 상태로 보고 각 상태별로 전이를 채워나간다.

글루시코프 작도는 톰슨 작도처럼 모듈을 연결하는 식으로 이루어지지는 않지만 여전히 각 문자의 소비 상태에만 의존하여 할 수 있으므로 단순하다.

같이 보기

• 오토마타 이론
• 톰슨 작도