임베디드 푸시다운 오토마톤

임베디드 푸시다운오토마톤(EPDA)은 TAG(Tree-Adjoin Grammars)에 의해 생성된 언어를 해석하기 위한 계산 모델입니다.이것은 문맥이 없는 문법 파싱 푸시다운 오토마톤과 비슷하지만 기호를 저장하기 위해 플레인 스택을 사용하는 대신 문맥이 없는 문맥과 문맥에 민감한 문맥 사이에 생성 용량을 TAG에 제공합니다.임베디드 푸쉬다운 오토마타는 계산 ^{[citation needed]}능력이 뛰어난 네스트된 스택 오토마타와 혼동하지 마십시오.

이력 및 응용 프로그램

EPDA는 K에 의해 처음 기술되었다.1988년 박사학위 ^[1]논문의 비제이 생커.그것들은 경미한 문맥에 민감한 문법의 종류에 대한 보다 완전한 설명에 적용되어 촘스키 계층 구조를 개선하는 데 중요한 역할을 해왔다.따라서 선형 색인 문법과 같은 다양한 하위 문법을 ^[2]정의할 수 있습니다.

자연어는 전통적으로 문맥이 없는 문법(변환 생성 문법 및 계산 언어학 참조)을 사용하여 분석되어 왔지만, 이 모델은 네덜란드어 등 EPDA가 적합한 교차 종속성이 있는 언어에는 적합하지 않습니다.상세한 언어 분석은 샤베스의 조시에서 구할 수 있다(1997).^[3]

이론.

EPDA는 임베디드 스택을 통해 액세스할 수 있는 스택 세트를 가진 유한 상태 머신입니다.각 스택에는 스택알파벳 $\,\Gamma$ \ $displaystyle$ , \ $Gamma$ 요소가 포함되어 있기 때문에 스택의 요소를 " $i$ _ ${i}\ in$ \ $Gamma$ 로 정의합니다.여기서 별은 알파벳의 클린 클로즈입니다.

그런 다음 각 스택을 요소의 관점에서 정의할 수 있으므로, : $\,\Upsilon _{j}=\ddagger \sigma _{j}=\{\sigma _{j,k},\sigma _{j,k-1},\ldots ,\sigma _{j,1}\}$ $\,\Upsilon _{j}=\ddagger \sigma _{j}=\{\sigma _{j,k},\sigma _{j,k-1},\ldots ,\sigma _{j,1}\}$ = $\,\Upsilon _{j}=\ddagger \sigma _{j}=\{\sigma _{j,k},\sigma _{j,k-1},\ldots ,\sigma _{j,1}\}$ = $\,\Upsilon _{j}=\ddagger \sigma _{j}=\{\sigma _{j,k},\sigma _{j,k-1},\ldots ,\sigma _{j,1}\}$ = $\,\Upsilon _{j}=\ddagger \sigma _{j}=\{\sigma _{j,k},\sigma _{j,k-1},\ldots ,\sigma _{j,1}\}$ { $\,\Upsilon _{j}=\ddagger \sigma _{j}=\{\sigma _{j,k},\sigma _{j,k-1},\ldots ,\sigma _{j,1}\}$ , $\,\Upsilon _{j}=\ddagger \sigma _{j}=\{\sigma _{j,k},\sigma _{j,k-1},\ldots ,\sigma _{j,1}\}$ , $\,\Upsilon _{j}=\ddagger \sigma _{j}=\{\sigma _{j,k},\sigma _{j,k-1},\ldots ,\sigma _{j,1}\}$ , $\,\Upsilon _{j}=\ddagger \sigma _{j}=\{\sigma _{j,k},\sigma _{j,k-1},\ldots ,\sigma _{j,1}\}$ - $\,\Upsilon _{j}=\ddagger \sigma _{j}=\{\sigma _{j,k},\sigma _{j,k-1},\ldots ,\sigma _{j,1}\}$ 1, $\,\Upsilon _{j}=\ddagger \sigma _{j}=\{\sigma _{j,k},\sigma _{j,k-1},\ldots ,\sigma _{j,1}\}$ $j$ , $\,\Upsilon _{j}=\ddagger \sigma _{j}=\{\sigma _{j,k},\sigma _{j,k-1},\ldots ,\sigma _{j,1}\}$ $}$ \ display $style$ , \ $Upsilon$ _ { j \ $jdd$ } $\ agger$ 기호를 사용하여 자동화의 j ${\$ $displaystyle$ = \ $\,j$ } $번째$ 스택을 $\,j$ . $\,\Upsilon _{j}=\ddagger \sigma _{j}=\{\sigma _{j,k},\sigma _{j,k-1},\ldots ,\sigma _{j,1}\}$ 여기서 " $\,\sigma _{j,k}$ "k $\$ "{ $j,k}"$ 는 $\,\sigma _{{j,k}}$ 스택에서 다음에 액세스할 수 있는 기호입니다.^{[clarification needed]}따라서 m $\,m$ {\ $displaystyle \,m}$ 스택의 $\,m$ $\,m$ 스택은 { $\,\{\Upsilon _{j}\}=\{\ddagger \sigma _{m},\ddagger \sigma _{m-1},\ldots ,\ddagger \sigma _{1}\}\in (\ddagger \Gamma ^{+})^{*}$ j } = $\,\{\Upsilon _{j}\}=\{\ddagger \sigma _{m},\ddagger \sigma _{m-1},\ldots ,\ddagger \sigma _{1}\}\in (\ddagger \Gamma ^{+})^{*}$ { $\,\{\Upsilon _{j}\}=\{\ddagger \sigma _{m},\ddagger \sigma _{m-1},\ldots ,\ddagger \sigma _{1}\}\in (\ddagger \Gamma ^{+})^{*}$ $\,\{\Upsilon _{j}\}=\{\ddagger \sigma _{m},\ddagger \sigma _{m-1},\ldots ,\ddagger \sigma _{1}\}\in (\ddagger \Gamma ^{+})^{*}$ m $\,\{\Upsilon _{j}\}=\{\ddagger \sigma _{m},\ddagger \sigma _{m-1},\ldots ,\ddagger \sigma _{1}\}\in (\ddagger \Gamma ^{+})^{*}$ $\,\{\Upsilon _{j}\}=\{\ddagger \sigma _{m},\ddagger \sigma _{m-1},\ldots ,\ddagger \sigma _{1}\}\in (\ddagger \Gamma ^{+})^{*}$ m - $\,\{\Upsilon _{j}\}=\{\ddagger \sigma _{m},\ddagger \sigma _{m-1},\ldots ,\ddagger \sigma _{1}\}\in (\ddagger \Gamma ^{+})^{*}$ + $\,\{\Upsilon _{j}\}=\{\ddagger \sigma _{m},\ddagger \sigma _{m-1},\ldots ,\ddagger \sigma _{1}\}\in (\ddagger \Gamma ^{+})^{*}$ ） $∗$ { \ $displaystyle$ \ , \ { \ $Upsilon$ _ { j } $=$ \ \ \ $dd$ \ dd \ $dd$ \ $agger$ } }로 나타낼 수 있습니다 $.$

EPDA는 Septuple(7-tuple)로 정의한다.

M =

(

\,M=(Q,\Sigma ,\Gamma ,\delta ,q_{0},Q_{\textrm {F}},\sigma _{0})

,

\,M=(Q,\Sigma ,\Gamma ,\delta ,q_{0},Q_{\textrm {F}},\sigma _{0})

, ,

\,M=(Q,\Sigma ,\Gamma ,\delta ,q_{0},Q_{\textrm {F}},\sigma _{0})

, ,

\,M=(Q,\Sigma ,\Gamma ,\delta ,q_{0},Q_{\textrm {F}},\sigma _{0})

\,M=(Q,\Sigma ,\Gamma ,\delta ,q_{0},Q_{\textrm {F}},\sigma _{0})

,

\,M=(Q,\Sigma ,\Gamma ,\delta ,q_{0},Q_{\textrm {F}},\sigma _{0})

F ,

\,M=(Q,\Sigma ,\Gamma ,\delta ,q_{0},Q_{\textrm {F}},\sigma _{0})

0 ) ,

0

0

、

0

\,M=(Q,\Sigma ,\Gamma ,\delta ,q_{0},Q_{\textrm {F}},\sigma _{0})

0 （ Q , \

Sigma

, \

Gamma

, \

textrm

{

F }

, \

sigma _ 0 }

。

$(\displaystyle\,Q)$ 는 $\,Q$ 유한한 상태의 집합입니다.
$σ \$ displaystyle \ $\,\Sigma$ Sigma $\,\Sigma$ }는 입력 알파벳의 유한 세트입니다.
$δ(\$ displaystyle $\Gamma$ 는 유한 스택 알파벳입니다.
$\,q_{0}\in Q$ 0 $\,q_{0}\in Q$ { $displaystyle$ \ , $q$ _ { $0$ } \ $in$ Q }가 시작 $\,q_{0}\in Q$ 상태입니다.
$\,Q_{\textrm {F}}\subseteq Q$ F $\,Q_{\textrm {F}}\subseteq Q$ Q { $display$ style }, $Q_{\textrm$ {F $}}\subseteq Q}$ 는 $\,Q_{{\textrm {F}}}\subseteq Q$ 최종 상태의 집합입니다.
$\,\sigma _{0}\in \Gamma$ 0 $\,\sigma _{0}\in \Gamma$ ∈ $γ$ \ display \ $sigma _$ { 0 } \ $in$ \ $Gamma$ }는 $\,\sigma _{0}\in \Gamma$ 초기 스택 $\,\sigma _{0}\in \Gamma$ 입니다.
$S$ $Q\times$ \ $Sigma \times \Gamma \rightarrow$ S $}$ 는 $\,\delta :Q\times \Sigma \times \Gamma \rightarrow S$ 전이함수입니다. $\,S$ 서 S $\,Q\times (\ddagger \Gamma ^{+})^{*}\times \Gamma ^{*}\times (\ddagger \Gamma ^{+})^{*}$ $displaystyle$ \, $S)$ 는 $\,S$ Q $\,Q\times (\ddagger \Gamma ^{+})^{*}\times \Gamma ^{*}\times (\ddagger \Gamma ^{+})^{*}$ × ( $\,Q\times (\ddagger \Gamma ^{+})^{*}\times \Gamma ^{*}\times (\ddagger \Gamma ^{+})^{*}$ + ) $\,Q\times (\ddagger \Gamma ^{+})^{*}\times \Gamma ^{*}\times (\ddagger \Gamma ^{+})^{*}$ × $\,Q\times (\ddagger \Gamma ^{+})^{*}\times \Gamma ^{*}\times (\ddagger \Gamma ^{+})^{*}$ ( $\,Q\times (\ddagger \Gamma ^{+})^{*}\times \Gamma ^{*}\times (\ddagger \Gamma ^{+})^{*}$ $\,Q\times (\ddagger \Gamma ^{+})^{*}\times \Gamma ^{*}\times (\ddagger \Gamma ^{+})^{*}$ + ) $\,Q\times (\ddagger \Gamma ^{+})^{*}\times \Gamma ^{*}\times (\ddagger \Gamma ^{+})^{*}$ \ $displaystyle$ \ $times$ ( \ $dd$ \ Gam + * )^{ } 。

따라서 트랜지션 함수는 상태, 입력 문자열의 다음 기호 및 현재 스택의 상위 기호를 사용하여 다음 상태, 임베디드 스택에 푸시되어 팝되는 스택, 현재 스택의 푸시 및 팝핑, 다음 트랜지션에서 현재 스택으로 간주되는 스택을 생성합니다.보다 개념적으로 임베디드 스택은 푸시 및 팝되며, 현재 스택은 옵션으로 임베디드 스택에 푸시되고, 그 위에 원하는 다른 스택이 푸시됩니다.마지막 스택은 다음 반복 시 읽혀지는 스택입니다.따라서 스택은 현재 스택 위아래로 푸시할 수 있습니다.

특정 설정은 다음과 같이 정의됩니다.

\displaystyle \,C(M)=\{q,\Upsilon _{1}\ldots \Upsilon _{1},x_{2}\}\in Q\times (\dagger \Gamma ^{+}^*}\times \Sigma ^{*})

$\,q$ 서 $\,q$ q { $displaystyle$ $\,q$ \, $q$ $}$ 는 $\,q$ $\,\Upsilon$ $\,\Upsilon _{m}$ 현재 상태이고, $\,\Upsilon$ $υ$ { $displaystyle$ $\,\$ $Upsilon$ $}$ s는 내장 스택의 스택이며, 입력 $\,x=x_{1}x_{2}\in \Sigma ^{*}$ x $\,x=x_{1}x_{2}\in \Sigma ^{*}$ x 2 $\,x=x_{1}x_{2}\in \Sigma ^{*}$ { display style \ , $x _$ 1 } { $\,\Upsilon _{m}$ x $\,x=x_{1}x_{2}\in \Sigma ^{*}$ ∈ { $\,x=x_{1}x_{2}\in \Sigma ^{*}$ 1 } { x 1 $\,x=x_{1}x_{2}\in \Sigma ^{*}$ { x { x 1 } { x 1 } { x 1 } { x 1 } { x 1 } { x { { x 1 } { x 1 } {x} {x} {x $}$ {x} {x} {x} {x} { { { { { $yle \,x_{1}}$ 는 $\,x_{1}$ 머신에 의해 이미 처리된 문자열의 $\,x_{2}$ 이며 $\,x_{2}$ 2 $({$ 는 $\,x_{2}$ 처리되는 부분으로 헤드가 현재 읽혀진 기호입니다.빈 문자열 $\,\epsilon \in \Sigma$ σ $、$ \ $displaystyle$ \ , \ $epsilon \ in$ \ $Sigma }$ 는 $\,\epsilon \in \Sigma$ 종단 기호로서 암묵적으로 정의되어 있습니다.빈 문자열을 읽을 때 머신이 최종 상태일 경우 입력 문자열 전체가 받아들여지고 거부되지 않을 경우 입력 문자열 전체가 받아들여집니다.이러한 수용된 문자열은 언어의 요소이다.

\displaystyle \,L(M)=\left\{x\{0},\upsilon_{0},\rightarrow_{M}^{*},\{q_{\textrm {F}},\ldots \Upsilon_{1},\ldots\lon\}\rightsilon_{{M}\}\}\}\},\},\},\},\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\

$\,q_{\textrm {F}}\in Q_{\textrm {F}}$ 서 Q $\,q_{\textrm {F}}\in Q_{\textrm {F}}$ $\,q_{\textrm {F}}\in Q_{\textrm {F}}$ F $\,q_{\textrm {F}}\in Q_{\textrm {F}}$ \ $displaystyle$ \ , $q$ _ { \ $textrm$ { $F$ } \ $in Q$ _ { \ $textrm$ { $F$ } $\,\rightarrow _{M}^{*}$ $\,\rightarrow _{M}^{*}$ M ${\$ { $displaystyle$ \ , \ $rightarrow$ _ { M }^{ * $\,\rightarrow _{M}^{*}$ } } 에서는 $\,\rightarrow _{M}^{*}$ 문자열을 해석하는 데 필요한 횟수만큼 적용되는 변환 함수를 정의합니다.

EPDA에 대한 비공식 설명은 Joshi, Schabes(1997),^[3] 7장, 페이지 23-25에서도 확인할 수 있다.

k차 EPDA 및 Wear 계층

경미한 문맥에 민감한 클래스에 대응하는 보다 정확하게 정의된 언어 계층은 David J.에 의해 정의되었습니다.위어,^[4] 나빌 A의 작품을 바탕으로 해Khabbaz,^[5]^[6] Weir의 제어 언어 계층은 셀 수 있는 언어 클래스^[clarify] 집합의 격납 계층으로, 여기서 레벨 1은 컨텍스트 프리, 레벨 2는 트리 결합의 클래스와 다른 세 개의 문법이다.

계층 내 Level-k 언어의 속성 중 일부를 다음에 나타냅니다.

Level-k 언어가 Level-(k + 1) 언어 클래스에 올바르게 포함되어 있습니다.
level-k 언어는 O $O(n^{3\cdot 2^{k-1}})$ 3 $O(n^{3\cdot 2^{k-1}})$ $O(n^{3\cdot 2^{k-1}})$ - $O(n^{3\cdot 2^{k-1}})$ ) $O(n^{3\cdot 2^{k-1}})$ { $displaystyle$ O $(n^{3\cdot$ 2 $^{k-1})}$ 시간 $O(n^{3\cdot 2^{k-1}})$ $O(n^{3\cdot 2^{k-1}})$ 에 구문 분석할 수 있습니다.
Level-k에는 언어 $\{a_{1}^{n}\dotso a_{2^{k}}^{n}|n\geq 0\}$ { $\{a_{1}^{n}\dotso a_{2^{k}}^{n}|n\geq 0\}$ $\{a_{1}^{n}\dotso a_{2^{k}}^{n}|n\geq 0\}$ n … $\{a_{1}^{n}\dotso a_{2^{k}}^{n}|n\geq 0\}$ 2 $\{a_{1}^{n}\dotso a_{2^{k}}^{n}|n\geq 0\}$ $\{a_{1}^{n}\dotso a_{2^{k}}^{n}|n\geq 0\}$ 0 $}$ { $displaystyle$ \ { a _ { a _ { { { a $_$ { { { n $}^{ n$ }^\ $geq$ 0 $\{a_{1}^{n}\dotso a_{2^{k}}^{n}|n\geq 0\}$ 이 포함되어 $\{a_{1}^{n}\dotso a_{2^{k+1}}^{n}|n\geq 0\}$ { $\{a_{1}^{n}\dotso a_{2^{k+1}}^{n}|n\geq 0\}$ $\{a_{1}^{n}\dotso a_{2^{k+1}}^{n}|n\geq 0\}$ n ... $\{a_{1}^{n}\dotso a_{2^{k+1}}^{n}|n\geq 0\}$ k + $\{a_{1}^{n}\dotso a_{2^{k+1}}^{n}|n\geq 0\}$ n $\{a_{1}^{n}\dotso a_{2^{k+1}}^{n}|n\geq 0\}$ 0 $}$ { $displaystyle$ \ { a _ { a _ $n$ }^{ n }^{ n $}^{$ n }^{ n + 1 n }\ $dot$ { 2 n }\ dot { 2 n }\ dot }\ dot }}\ dot
$\{w^{2^{k-1}}|w\in \{a,b\}^{*}\}$ 에는 { $\{w^{2^{k-1}}|w\in \{a,b\}^{*}\}$ 2 $\{w^{2^{k-1}}|w\in \{a,b\}^{*}\}$ - $\{w^{2^{k-1}}|w\in \{a,b\}^{*}\}$ $\{w^{2^{k-1}}|w\in \{a,b\}^{*}\}$ $\{w^{2^{k-1}}|w\in \{a,b\}^{*}\}$ { $\{w^{2^{k-1}}|w\in \{a,b\}^{*}\}$ , $\{w^{2^{k-1}}|w\in \{a,b\}^{*}\}$ $\{w^{2^{k-1}}|w\in \{a,b\}^{*}\}$ { $\{w^{2^{k-1}}|w\in \{a,b\}^{*}\}$ { $displaystyle$ \ { $w^2$ $\{w^{2^{k-1}+1}|w\in \{a,b\}^{*}\}$ ^{ $k-1$ $}$ w\ $in$ \ {a $\{w^{2^{k-1}}|w\in \{a,b\}^{*}\}$ , $\{w^{2^{k-1}}|w\in \{a,b\}^{*}\}$ b \ $\{w^{2^{k-1}}|w\in \{a,b\}^{*}\}$ w가 포함되어 있지만 { $\{w^{2^{k-1}+1}|w\in \{a,b\}^{*}\}$ $\{w^{2^{k-1}+1}|w\in \{a,b\}^{*}\}$ - $\{w^{2^{k-1}+1}|w\in \{a,b\}^{*}\}$ + $\{w^{2^{k-1}+1}|w\in \{a,b\}^{*}\}$ w $\{w^{2^{k-1}+1}|w\in \{a,b\}^{*}\}$ { $\{w^{2^{k-1}+1}|w\in \{a,b\}^{*}\}$ , $\{w^{2^{k-1}+1}|w\in \{a,b\}^{*}\}$ } { a , b $\{w^{2^{k-1}+1}|w\in \{a,b\}^{*}\}$ w - 1 $\{w^{2^{k-1}+1}|w\in \{a,b\}^{*}\}$ { 1 } w - { 1 } w - { 1 } w - { 1 $\{w^{2^{k-1}+1}|w\in \{a,b\}^{*}\}$ } { 1 } { 1 } w - { $displaystyl$ } { $1$ } w - { 1 }}}}}} w -

이러한 특성은 (적어도 작은 k > 1) Joshi에 의해 부과된 경미한 문맥에 민감한 언어의 조건에 잘 부합하며, k가 커질수록 언어 클래스는 어떤 의미에서는 경미한 문맥에 덜 민감해진다.

「」를 참조해 주세요.

조합 범주형 문법

레퍼런스

^ Vijay-Shanker, K. (January 1988). "A Study of Tree-Adjoining Grammars". Ph.D. Thesis. University of Pennsylvania.
^ Weir, David J. (1994). "Linear Iterated Pushdowns" (PDF). Computational Intelligence. 10 (4): 431–439. doi:10.1111/j.1467-8640.1994.tb00007.x. Retrieved 2012-10-20.
^ ^a ^b Joshi, Aravind K.; Yves Schabes (1997). "Tree-Adjoining Grammars" (PDF). Handbook of Formal Languages. Springer. 3: 69–124. doi:10.1007/978-3-642-59126-6_2. ISBN 978-3-642-63859-6. Retrieved 2014-02-07.
^ Weir, D. J. (1992), "A geometric hierarchy beyond context-free languages", Theoretical Computer Science, 104 (2): 235–261, doi:10.1016/0304-3975(92)90124-X.
^ Nabil Anton Khabbaz (1972). Generalized context-free languages (Ph.D.). University of Iowa.
^ Nabil Anton Khabbaz (1974). "A geometric hierarchy of languages". J. Comput. Syst. Sci. 8 (2): 142–157. doi:10.1016/s0022-0000(74)80052-8.

추가 정보

Laura Kallmeyer (2010). Parsing Beyond Context-Free Grammars. Springer Science & Business Media. ISBN 978-3-642-14846-0.

[1] Vijay-Shanker, K. (January 1988). "A Study of Tree-Adjoining Grammars". Ph.D. Thesis. University of Pennsylvania.

[2] Weir, David J. (1994). "Linear Iterated Pushdowns" (PDF). Computational Intelligence. 10 (4): 431–439. doi:10.1111/j.1467-8640.1994.tb00007.x. Retrieved 2012-10-20.

[Joshi.Schabes.1997-3] Joshi, Aravind K.; Yves Schabes (1997). "Tree-Adjoining Grammars" (PDF). Handbook of Formal Languages. Springer. 3: 69–124. doi:10.1007/978-3-642-59126-6_2. ISBN 978-3-642-63859-6. Retrieved 2014-02-07.

[4] Weir, D. J. (1992), "A geometric hierarchy beyond context-free languages", Theoretical Computer Science, 104 (2): 235–261, doi:10.1016/0304-3975(92)90124-X.

[5] Nabil Anton Khabbaz (1972). Generalized context-free languages (Ph.D.). University of Iowa.

[6] Nabil Anton Khabbaz (1974). "A geometric hierarchy of languages". J. Comput. Syst. Sci. 8 (2): 142–157. doi:10.1016/s0022-0000(74)80052-8.

[1]

[2]

[3]

[4]

[5]

[6]

Search

임베디드 푸시다운 오토마톤

네임스페이스

더

목차

이력 및 응용 프로그램

이론.

k차 EPDA 및 Wear 계층

「」를 참조해 주세요.

레퍼런스

추가 정보

Search

임베디드 푸시다운 오토마톤

이력 및 응용 프로그램

이론.

k차 EPDA 및 Wear 계층

「 」를 참조해 주세요.

레퍼런스

추가 정보

「」를 참조해 주세요.