결정론적 푸시다운 오토마톤

오토마타 이론에서 결정론적 푸시다운 오토마톤(DPDA 또는 DPA)은 푸시다운 오토마톤의 변형이다.결정론적 푸시다운 오토마타의 클래스는 결정론적 문맥 자유 언어,^[1] 즉 문맥 자유 언어의 적절한 하위 집합을 받아들인다.

기계 전환은 현재 상태 및 입력 기호와 스택의 현재 맨 위 기호를 기반으로 합니다.스택 아래쪽에 있는 기호는 표시되지 않으며 즉각적인 효과는 없습니다.머신 동작에는 스택톱의 푸시, 팝핑 또는 교환이 포함됩니다.결정론적 푸시다운 오토마톤은 입력 기호, 상태 및 탑 스택 기호의 동일한 조합에 대해 최대 1개의 법적 전환을 가집니다.이것이 비결정론적 푸시다운 오토마톤과 다른 점이다.

형식적 정의

$PDA{\displaystyle }$ M$(확정적$이지는 않지만$)$은 7 태플로서 정의할 수 있습니다.

$({displaystyle M=(Q,\Sigma,\Gamma,,q_{0},Z_{0},A,\delta,})$

어디에

• $(\$ Q$,)$는 유한한 상태의 집합입니다.
• $σ${ $displaystyle$ \ Sigma$$}는$$ 입력 ${\displaystyle \mathrm{기호}}$의 유한 세트입니다.
• $γ${ $displaystyle$ \ Gamma$$}는 스택 기호의 유한 세트입니다.
• ${\displaystyle {q\mathrm{}}_{}}$ 0${\displaystyle {}_{}\mathrm{qQ}}$( \ $displaystyle q$_ { 0$$} , \ $in$ Q$$)는$$ 시작 ${\displaystyle {\mathrm{스테이트}}_{}}$입니다.
• ${\displaystyle {Z\mathrm{}}_{}}$ 0 ${\displaystyle \in {}_{}}$ $display$ \style $Z_{0},\in \Gamma,\}$는 시작 스택 기호입니다.
• $(\$ A$,\subseteq$ Q$,)$ ($여기$서$$A(\$displaystyle$ A$)$는 수용 또는 최종 상태의 집합)
• $§$ (\$displaystyle$\displaystyle$\$display, )는 이행 함수입니다.

$\displaystyle \delta \colon (Q,\times (\Sigma \left \{\varepsilon \,\right \})\times \Gamma \}\long rightarrow (Q\times \Gammathcal {P}})$

여기서$【{displaystyle *}$은 Kleene 별입니다.$이것$은 $【\$$displaystyle \Gamma$^{*}】이 【\$displaystyle \Gamma 】$요소의 $모든{\displaystyle }$ 유한 문자열(\displaystyle \$varepsilon$$}$ $포함{\displaystyle }$)】,${\displaystyle }$【\$displaystyle \varepsilon】$는 「$X{\displaystyle \mathcal{}}$」의 빈 문자열의 집합입니다.$${\$displaystyle$ ${P}}(X$$)$는 $X$의 파워셋입니다$.$

M은 다음 조건을 모두 만족하는 경우 결정론적이다.

• $임의$의 ${\displaystyle Q,}$ $Q$ Q$,$ $, Sigma \cup$\left \{\$varepsilon$\right$\}, x\in$ \Gamma$$}에 대해 $세트{\displaystyle }$ ${\displaystyle (}$ (${\displaystyle q}$ , a ,${\displaystyle }$x $)\$x )가 있습니다$.$
• $임의$의${\displaystyle Q,}$ ${\displaystyle \mathrm{x}}$에 대해$$($varepsilon$, x${\displaystyle )<img\; alt="q\backslash in\; Q,x\backslash in\; \backslash Gamma\; "\; aria-hidden="true"\; class="mwe-math-fallback-image-inline"\; src="https://wikimedia.org/api/rest\_v1/media/math/render/svg/a8bf1f9419ebc33f421d02b2c79122b1cfafc511"\; style="vertical-align:\; -0.671ex;\; width:12.406ex;\; height:2.509ex;">}$\$displaystyle$ \displaystyle $\display(q,\$varepsilon$,x$$not$ ${\displaystyle =\backslash }$$emptyset,\$display(${\displaystyle q,a,x)\backslash }$displaystyle$=\display(x$)\displaystyle \displaystyle(q,x)\displaystyle\display(x$)\$displaystyle\dispon,x)\display =\displaystyle\$d$

가능한 허용 기준은 빈 스택에 의한 허용과 최종 상태에 의한 허용 두 가지가 있습니다.두 가지는 결정론적 푸시다운 오토마톤에 대해 동일하지 않다(비결정론적 푸시다운 오토마톤에 대한 것이지만).빈 스택에 의해 받아들여지는 언어는 최종 스테이트에서 받아들여지고 프리픽스가 없는 언어입니다.^{[citation needed]}언어 내의 단어는 언어 내의 다른 단어의 프리픽스입니다.

일반적인 허용 기준은 최종 상태이며, 결정론적 문맥 자유 언어를 정의하기 위해 사용되는 것이 이 허용 기준이다.

인식되는 언어

L$)$ {$displaystyle$ L$(A$$)}$이($가$$)$ $PDA{\displaystyle }$ A {$displaystyle$ A$\}$에 의해 받아들여지는 언어일 $경우{\displaystyle }$ 초기 설정부터${\displaystyle }$$L$${\displaystyle (}$A$)$에 속하는 모든 문자열에 대해 받아들여질 때까지의 연산이1개만 있는 $경우$에만 DPDA에 의해 받아들여질 수 있습니다$.$PDA에 의해 암호화되는 것은 컨텍스트프리 언어이며, DPDA에 의해 받아들여질 수 있는 경우는 결정론적 컨텍스트프리 언어(DCFL)입니다.

모든 문맥이 없는 언어가 결정론적인 것은 아닙니다.따라서 DPDA는 PDA보다 훨씬 약한 디바이스입니다.만약 DPDA 이 언어의 예를 들어,even-length palindromes의 0과 1의 알파벳으로 언어 Lp고, 문자열 중·소도시 택지 공급 사업 보는 문맥 자유 문법 S→ 0S0 1S1 ε 위해 ∈ Lp와 중·소도시 택지 공급 사업 110n+2 ∉ Lp가 가능한 continuations 중·소도시 택지 공급 사업 11중·소도시 택지 공급 사업 구별할 수 있는 길이 n를 많이 외우는 것은 스택을 사용해야만 한다.따라서, 후에 독서 중·소도시 택지 공급 사업 11ⁿ 0 이후의 길이를 11 이전의 길이와 비교하면 스택이 다시 비게 됩니다.따라서ⁿ 문자열 0 11ⁿ 0ⁿ 0 11ⁿ l_p L과ⁿ 0 11ⁿ 0ⁿ⁺² 0 11ⁿ⁺² l_p L은 ^[2]구분할 수 없습니다.

DPDA를 단일 상태로 제한하면 DCFL의 ^[4]적절한 서브클래스인 LL(1) ^[3]언어에 허용되는 언어 클래스가 줄어듭니다.PDA 의 경우, 이 제한은, 허가된 언어의 클래스에는 영향을 주지 않습니다.

특성.

클로즈

결정론적 문맥이 없는 언어(최종 상태에 의해 결정론적 PDA에 의해 수용됨)의 폐쇄 특성은 문맥이 없는 언어와 크게 다르다.예를 들어, 상호 보완 하에서는 (효과적으로) 폐쇄되지만, 결합 하에서는 폐쇄되지 않는다.결정론적 PDA에 의해 받아들여진 언어의 보완이 결정론적 PDA에 의해 받아들여진다는 것을 증명하는 것은 어렵다.^{[citation needed]}원칙적으로 무한연산을 피해야 한다.

보완의 결과로서 결정론적 PDA가 그 입력 알파벳 위에 모든 단어를 받아들이는지 아닌지는 그 보완을 시험함으로써 판단할 수 있다.이것은 문맥이 없는 문법에 대해서는 가능하지 않습니다(따라서 일반 PDA에는 해당되지 않습니다).

동등성 문제

Géraud Sénizergues(1997)는 결정론적 PDA(즉, 두 개의 결정론적 PDA A와 B가 주어졌을 때 L(A)=L(B)?)에 대한 동등성 문제가 ^[5][6][7]결정 가능하다는 것을 증명했으며, 이는 2002년 괴델 상을 받은 증거이다.비결정론적 PDA의 경우 등가성은 판별할 수 없습니다.

메모들

추가 정보

• Hamburger, Henry; Dana S. Richards (2002). Logic and Language Models for Computer Science. Upper Saddle River, NJ 07458: Prentice Hall. pp. 284–331. ISBN 0-13-065487-6.{{cite book}}: CS1 유지보수: 위치(링크)