스레드 오토마톤

Thread automaton

오토마타 이론에서, 스레드 오토마톤(복수: 오토마타)은 트리 결합 [1]언어 위에 약간의 문맥에 민감한 언어 클래스를 인식하는 유한 상태 오토마타의 확장된 유형이다.

형식적 정의

스레드 오토마톤은 다음과 같이 구성됩니다.

  • 일련의 N개의 주,[note 1]
  • 단자 기호 세트 δ,
  • 시작 상태S A n N,
  • 최종 상태F A n N,
  • U의 패스 컴포넌트 세트,
  • 부분 함수 θ: N → U⊥, 여기서⊥ U = U { U에 대해 {timeout},
  • 유한한 천이집합 δ.

경로1 u...un u* U는 경로 성분i u u U의 문자열입니다.n은 0일 수 있으며 빈 경로는 ε로 표시됩니다.스레드의 형식은1 un...u:A이며, 여기서1 u...un u* U는 패스, A n N은 스테이트이다.스레드 스토어 S는 U에서* N까지의 부분 함수로서 dom(S)이 프리픽스로 닫히는 유한한 스레드 집합이다.

스레드 오토마톤 구성은 트리플 'l,p,S'입니다.여기서 l은 입력 문자열의 현재 위치를 나타내고 p는 액티브 스레드, S는 p를 포함하는 스레드 스토어입니다.초기 설정은 「0,」, 「{」입니다.AS}」. 최종 구성은 「n,u,{」:AS,u:AF}' 여기서 n은 입력 문자열의 길이이고 u는 "(AS)"를 생략합니다.세트 θ의 이행은 다음 중 하나의 형식을 가지며 현재 자동 설정을 다음과 같이 변경할 수 있습니다.

  • SWAP B →a C: 입력 기호 a를 소비하고 활성 스레드의 상태를 변경합니다.
는 설정을 "l,p,S"에서 변경합니다.{ p :B}'에서 "l+1,p,S"로 {p:C}★
  • SWAP B →ε C: 유사하지만 입력을 소비하지 않습니다.
변경 "l,p,S"{p:B}'에서 "l,p,S"로 {p:C}★
  • PUSH C: 새 서브스레드를 만들고 부모 스레드를 일시 중단합니다.
변경 "l,p,S"{p:B}에서 "l,pu,S"로 {p:B,pu:C}로 이동합니다. 여기서 u=pu(B) 및 pu(s)dom(S)
  • POP [B]C: 활성 스레드를 종료하고 부모에게 제어권을 반환합니다.
"l,pu,S" {p:B,pu:C}"를 "l,p,S"로 변경합니다.C } where 、 （ C ） = ∉∉( pu pu pu pu(dom ( S )
  • SPUSH [C] D: 활성 스레드의 일시 중단된 하위 스레드를 재개합니다.
"l,p,S" "{p:B,pu:C}" 를 "l,pu,S" {p:B,pu:C} 로 변경합니다.D}개요 여기서 u=개요(B)
  • SPOP [B] D: 활성 스레드의 부모를 재개합니다.
"l,pu,S"{p:B,pu:C}"를 "l,p,S"{p:D,pu:C}"로 변경합니다.여기서 "(C)="

POP 및 SPOP 천이의 경우 ((B)=u, SPUSH [2]천이의 경우 c(C)= for임을 증명할 수 있다.

입력 문자열은 첫 번째 구성을 최종 구성으로 변경하는 일련의 천이가 있는 경우 자동화에 의해 받아들여진다.

메모들

  1. ^ Vilmonte(2002), 페이지 1r에 의한 비터미널 심볼이라고 불림

레퍼런스

  1. ^ Villemonte de la Clergerie, Éric (2002). "Parsing mildly context-sensitive languages with thread automata". COLING '02 Proceedings of the 19th International Conference on Computational Linguistics. 1 (3): 1–7. doi:10.3115/1072228.1072256. Retrieved 2016-10-15.
  2. ^ 빌몬테 (2002), 페이지 1r-2r