트리 스택 오토마톤

Tree stack automaton

트리 스택[a] 오토마톤(복수: 트리 스택 오토마타)은 오토마타 이론에서 고려되는 형식주의입니다.이것은 트리 모양의 스택을 조작할 수 있는 추가 기능을 가진 유한 상태 오토마톤입니다.스토리지 구성이 스레드 자동화와 거의 비슷한 스토리지를 사용하는[2] 자동화입니다.제한된 클래스의 트리 스택 오토마타는 멀티 콘텍스트프리[3] 문법(또는 리니어 콘텍스트프리 리라이트 시스템)에 의해 생성된 언어를 정확하게 인식합니다.

정의.

트리 스택

스택 포인터 1.2 및 도메인 {domain, 1, 42, 1.2, 1.5, 1.5.3을 가진 트리 스택}

유한하고 비어 있지 않은 집합 δ의 경우, 트리 스택 오버는 태플(t, p)입니다.

  • tprefix-closed 도메인(트리라고 함)을[b] 사용하여 정의 정수의 문자열에서 집합 δ δ {@}까지의 부분 함수입니다.
  • @(하단 기호라고 함)은 δ에 없고 t의 루트에 정확하게 표시됩니다.
  • p는 t 도메인의 요소(스택 포인터라고 불립니다)입니다.

γ 위의 모든 트리 스택의 세트는 TS(γ)표시됩니다.

TS(δ)술어 세트(Pred(δ))에는 다음과 같은 단항 술어가 포함되어 있습니다.

  • trueγ 위의 모든 트리 스택에 해당됩니다.
  • 스택 포인터가 아래쪽 기호를 가리키는 트리 스택에 해당됩니다.
  • t(p) = γγγγ tγγ t t t t t t t t t t t ( ( ( ( ( ((t, p)의 일부 트리 스택(t, p)에 대해 해당된다.

γevery every every every every every 。

TS(()명령어 세트(Instr(γ)로 표시됨)에는 다음과 같은 부분 기능이 포함되어 있습니다.

  • id: TS(TX) TS(TX)식별 함수인 TS(TX)
  • 푸시n,γ: TS(δ) TS(δ) - 특정 트리 스택(t,p)에 대해 쌍(pn δ)트리 t에 추가하고 pn이 아직 t의 도메인에 없는 경우 스택 포인터를 pn으로 설정합니다(, pn을 n번째 자 위치로 푸시합니다).
  • upn: TS(δ) TS(δ) - 현재 스택 포인터pn으로 대체(즉, pn이 t의 영역에 있는 경우 스택 포인터를 n번째 자 위치로 이동),
  • down: TS(δ) TS(δ) 스택 포인터에서 마지막 기호를 제거합니다(즉, 스택 포인터를 부모 위치로 이동).
  • 세트γ: TS(δ) TS(δ)는 현재 스택 포인터 아래에 있는 기호를 δ로 바꿉니다.

모든 양의 정수 n 및 모든 γ every every every every 。

트리 스택의 명령 ID 그림
트리 스택의 명령 푸시 그림
트리 스택 위의 위아래 명령 그림
트리 스택의 명령 세트 그림

트리 스택 오토마타

트리 스택 오토마톤은 6 태플A = (Q, γi, ,, ,, q, ,, Q) 입니다f.

  • Q, δδ는 유한 집합(각각 상태, 스택 기호 및 입력 기호라고 불립니다)입니다.
  • qi q Q (초기 상태),
  • δ fin.Q × (σ ∪ {ε}) × Pred()) × Instr()) × Q (어떤 요소를 전이라고 하는가)
  • Qf ts TS()) (요소를 최종 상태라고 부릅니다.)

의 설정은 다음과 같은 태플(q, c, w)입니다.

  • q는 상태(현재 상태)입니다.
  • c는 트리 스택(현재 트리 스택)입니다.
  • w는 단어 over δ(읽는 나머지 단어)입니다.

이행 = (q1, u, p, f, q2)는, 다음의 경우에 설정(q, c, w)적용할 수 있습니다.

  • q = q1,
  • pc에서는 true입니다.
  • f는 c에 대해 정의됩니다.
  • uw의 프리픽스입니다.

의 전이관계는 의 구성에 있어서의 바이너리관계 θ이며, 전이관계 τθ = (q1, u, p, f, q2)에 θ가 적용 가능한 경우에는 항상 (q, c, w) τθ(q2, f(c, v)가지며, 프리픽스 u를 제거하여 w에서 v를 얻는다.

의 언어는 모든 단어 세트입니다.여기서는 상태q' Qf트리 스택c가 있고i (qi, c,* w) (q, c, ")가 있습니다.

  • θ는 θ의 반사적 과도 폐쇄이다.*
  • ci = (ti, ε)는 t가 기호i @를 할당하고 달리 정의되지 않은 경우입니다.

관련 형식

트리 스택 오토마타는 튜링 머신과 동일합니다.

트리 스택 오토마톤은 오토마톤 실행 중 트리 스택의 위치에 아래에서 최대 k번 접근하면 양의 자연수에 대해 -Restricted라고 불립니다.

1회차 트리 스택 오토마타는 푸시다운 오토마타와 동등하며, 따라서 컨텍스트가 필요 없는 문법과도 같습니다.k회차 트리 스택 오토마타는 최대 k개의 팬아웃의 리라이트 시스템 및 멀티콘텍스트가 필요 없는 문법과 동등합니다(정의 정수 [3]k개당).

메모들

  1. ^ 볼프강 골럽스키와 울프램-M이 1990년에 도입한 같은 이름의 장치와 혼동하지 마십시오.리페
  2. ^ 문자열 세트는 세트 내의 모든 요소 w에 대해 w의 모든 프레픽스도 세트 내에 있는 경우 prefix-closed가 됩니다.

레퍼런스

  1. ^ 골럽스키, 볼프강, 리페, 울프람-M.(1990년).트리 스택 오토마타제15회 컴퓨터 사이언스 수학 기초 심포지엄(MFCS 1990)의 속행.컴퓨터 공학 강의 노트, 제452권, 313~321쪽, doi:10.1007/BF0029624.
  2. ^ 스콧, 다나(1967).오토마타 이론에 대한 몇 가지 정의적 제안.컴퓨터 및 시스템 과학 저널, 제1(2), 187~212쪽, doi:10.1016/s0022-0000(67)80014-x.
  3. ^ a b Denkinger, Tobias(2016).문맥이 없는 여러 언어의 자동 특성화.제20회 언어이론 발전 국제회의(DLT 2016) 진행.컴퓨터 공학 강의 노트, 제9840권, 138-150쪽, doi:10.1007/978-3-662-53132-7_12.