중첩된 스택 자동화
Nested stack automaton
오토마타 이론에서 중첩된 스택 오토마톤은 추가 [1]스택이 될 수 있는 데이터를 포함하는 스택을 사용할 수 있는 유한 오토마톤이다.스택 오토마톤과 마찬가지로 네스트된 스택 오토마톤은 스택 내에서 스텝업 또는 다운하여 현재 심볼을 읽을 수 있습니다.또, 어느 장소에서나 새로운 스택을 작성하고, 그 스택으로 동작해, 최종적으로 파기해, 낡은 스택으로 동작을 계속할 수 있습니다.이렇게 하면 스택을 임의의 깊이로 재귀적으로 중첩할 수 있지만 자동화는 항상 가장 안쪽 스택에서만 작동합니다.
중첩된 스택오토마톤은 인덱스된 [2]언어를 인식할 수 있으며, 실제로 인덱스된 언어의 클래스는 단방향 비결정론적 중첩된 스택오토마타에 [1][3]의해 받아들여지는 언어의 클래스입니다.
중첩된 스택 오토마타는 계산 능력이 낮은 [citation needed]삽입형 푸시다운 오토마타와 혼동해서는 안 됩니다.
형식적 정의
오토마톤
(비결정적 쌍방향) 네스트된 스택오토마톤은 태플 'Q', '', '', 'Q0', 'Q0', 'Z', 'F', ',' 입니다.
- Q, δ 및 δ는 각각 비어 있지 않은 유한 상태 집합, 입력 기호 및 스택 기호입니다.
- [, ] 및 ]는 σ ∪ ∪ , contained contained 에는 포함되지 않은 별개의 특수 기호입니다.
- [ ] 는 입력 문자열과 (서브)스택 문자열의 양쪽에서 왼쪽 엔드마커로 사용됩니다.
- ] 는, 이러한 문자열의 오른쪽 엔드 마커로서 사용됩니다.
- ] 는 [note 1]스택 전체를 나타내는 문자열의 마지막 엔드마커로 사용됩니다.
- 확장 입력 알파벳은 σ' = { ' { [ , ] , 확장 스택 알파벳은 γ ' = { { ] , 입력 이동 방향 집합은 D = {-1,0,+1}로 정의됩니다.
- 유한 제어인 δ는 Q × δ' × (δ' ∪ [ δ ' { { , [ ] )에서 Q × D × ([ δ* ), D)의 유한 부분 집합으로의 매핑으로, 다음과 같이[note 2] δ 맵을 나타낸다.
| Q × σ' × [ q] | Q × D × γ* [ of ]의 서브셋으로 분류한다. | (다운 모드), | |
| Q × σ' × γ' | Q × D × D의 하위 집합으로 | (읽기 모드), | |
| Q × σ' × [ ''] | Q × D × {+1}의 하위 집합으로 전환 | (읽기 모드), | |
| Q × Ω' × {]} | Q × D × {-1}의 하위 집합으로 분류 | (읽기 모드), | |
| Q × σ' × (γ' ∪ [)') | Q × D × [δ*]의 서브셋으로 분류한다. | (스택 작성 모드) 및 | |
| Q × σ' × {[]} | Q × D × {},}의 하위 집합으로 이동합니다. | (스택 파괴 모드), |
- 비공식적으로 (서브)스택의 상단 기호와 앞의 왼쪽 엔드마커 ""[4]는 단일 기호로 표시되며, 그 후 reads가 읽힙니다.
- 현재 상태,
- 현재 입력 기호 및
- 현재 스택 기호,
- 및 출력
- 다음 주,
- 입력에서 이동할 방향 및
- 스택에서 이동할 방향 또는 맨 위 스택 기호를 대체할 기호 문자열.
- q qQ는0 초기 상태입니다.
- Z0 ∈ is the는 초기 스택 기호입니다.
- F q Q는 최종 상태의 집합입니다.
배열
이러한 오토마톤에 대한 구성 또는 즉각적인 설명은 트리플 µ q, [aa12...ai...an-1], [ZX12...Xj...]로 구성됩니다.Xm-1] ,, 여기서
- q qQ는 현재 상태입니다.
- [aa12...ai...an-1]는 입력 문자열입니다. 편의상 a = [ 및 an = ]가0[note 3] 정의됩니다. 입력의 현재 위치 viz. i는 0 µ i µ n으로 각 기호를 밑줄로 표시합니다.
- [ZX12...Xj...X...]X]는m-1 하위 스택을 포함한 스택입니다. 편의상 X = [Z1 및 Xm = ]가1 정의됩니다.스택의 현재 위치인 viz. j는 1µj µm로 각 기호를 밑줄로 표시합니다.
예
실행 예(입력 문자열은 표시되지 않음):
| 액션. | 걸음 | 스택 | |||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 1: | [a] | b | [k] | ] | [p] | ] | c | ] | |||||
| 서브팩을 작성하다 | 2: | [a] | b | [k] | ] | [p] | [r] | s | ] | ] | c | ] | |
| 팝 | 3: | [a] | b | [k] | ] | [p] | [s] | ] | ] | c | ] | ||
| 팝 | 4: | [a] | b | [k] | ] | [p] | [] | ] | c | ] | |||
| 서브팩을 파괴하다 | 5: | [a] | b | [k] | ] | [p] | ] | c | ] | ||||
| 아래로 이동하다 | 6: | [a] | b | [k] | ] | [p] | ] | c | ] | ||||
| 승진하다 | 7: | [a] | b | [k] | ] | [p] | ] | c | ] | ||||
| 승진하다 | 8: | [a] | b | [k] | ] | [p] | ] | c | ] | ||||
| 밀다 | 9: | [a] | b | [k] | ] | [n] | o | p | ] | c | ] | ||
특성.
오토마타가 입력('쌍방향 오토마타')을 다시 읽을 수 있는 경우, 네스트된 스택에서는 일반 [5]스택과 달리 언어 인식 기능이 추가되지 않습니다.
Gilman과 Shapiro는 [6]중첩된 스택 오토마타를 사용하여 특정 그룹의 단어 문제를 해결했습니다.
메모들
- ^ 아호는 원래 "[]"와 "]" 대신에 "$", "","과 "#"을 각각 사용했다.Aho(1969), 페이지 385 상단을 참조하십시오.
- ^ Juxataposition은 문자열(세트) 연결을 나타내며 set union ∪보다 바인딩 우선순위가 높습니다.예를 들어 [δ]는 ""로 시작하여 δ"에서 기호로 끝나는 모든 길이-2 문자열의 집합을 나타냅니다.
- ^ Aho는 원래 좌우 스택 마커인 viz를 사용했습니다.오른쪽 및 왼쪽 입력 마커로서의 $와 ,.
- ^ (서브) 스택의 맨 위 기호와 앞의 왼쪽 엔드 마커는 단일 기호로 표시됩니다.
레퍼런스
- ^ a b Aho, Alfred V. (July 1969). "Nested Stack Automata". Journal of the ACM. 16 (3): 383–406. doi:10.1145/321526.321529. S2CID 685569.
- ^ Partee, Barbara; Alice ter Meulen; Robert E. Wall (1990). Mathematical Methods in Linguistics. Kluwer Academic Publishers. pp. 536–542. ISBN 978-90-277-2245-4.
- ^ John E. Hopcroft, Jeffrey D. Ullman (1979). Introduction to Automata Theory, Languages, and Computation. Addison-Wesley. ISBN 0-201-02988-X. 여기:p.390
- ^ 아호(1969), 385쪽 윗면
- ^ Beeri, C. (June 1975). "Two-way nested stack automata are equivalent to two-way stack automata". Journal of Computer and System Sciences. 10 (3): 317–339. doi:10.1016/s0022-0000(75)80004-3.
- ^ Shapiro, Robert Gilman Michael (4 December 1998). On groups whose word problem is solved by a nested stack automaton (Technical report). arXiv:math/9812028. CiteSeerX 10.1.1.236.2029. S2CID 12716492.
