글루시코프 작도

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

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

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

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

쉬운 작도법

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

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

같이 보기

편집