글루시코프 작도 문서 원본 보기

{{위키데이터 속성 추적}}
'''글루시코프 작도'''(Glushkov -)는 1960년 [[글루시코프]]가 제안한 [[정규 표현식]]에서 유한 [[오토마타 이론|오토마타]]<!--[[유한 오토마타]] 생성 후엔 여기로 걸기 -->를 얻는 작도법이다. [[톰슨 작도]]보다 복잡하지만 <math>\epsilon</math>변환을 만들지 않는다.

글루시코프 작도는 다음 특징이 있다.
#<math>\epsilon</math>변환이 없다.
#시작 상태는 내변환이 없다.
#각 상태의 모든 내변환은 같은 레이블을 갖는다.
#상태의 수는 정규 표현식의 기호 수보다 하나가 더 많다.

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

== 쉬운 작도법 ==
#정규 표현식의 각 리터럴에 상태를 부여한다.
#시작 상태를 추가한다.
#각 상태를 해당 리터럴을 소비한 상태로 보고 각 상태별로 전이를 채워나간다.
글루시코프 작도는 톰슨 작도처럼 모듈을 연결하는 식으로 이루어지지는 않지만 여전히 각 문자의 소비 상태에만 의존하여 할 수 있으므로 단순하다.

== 같이 보기 ==
* [[오토마타 이론]]
* [[톰슨 작도]]

{{토막글|컴퓨터 과학}}

[[분류:형식 언어]]