가능한 모든 DCFL을 생성하기에 충분히 강력한 S-Grammar입니까?

Question

s-grammar의 모든 프로덕션은 A → 𝑎𝛼 , A∈V , a∈T , 𝛼∈V*

의 형태입니다.

"... 그리고 어떤 쌍 (a, a)은 p를 가장 많이 발생합니다." [p. Linz, 6th ed. , p. 144]

s-grammar는 모호하지 않으며 S-grammar의 모든 모호하지 않은 -CFL을 모두 설명 할 수 있다고 생각합니다. s-grammar가 모든 가능한 DCFL을 묘사 할 수 있습니까? 이 문장에 따르면, 나는 그것을 할 수는 없다고 생각하지만 그것에 대해 확신하지 못한다고 생각합니다 :

불행히도, 일반적인 프로그래밍 언어의 모든 기능을 S-Grammar에 의해 표현할 수있는 것은 아닙니다. [p. Linz, 6th ed. , p. 152]

그러나 s-grammar가 설명한 모든 언어는 결정적 입니다.

이 정의가있는 간단한 문법에 대해 2 개의 상태 DPDA를 만들 수 있기 때문에 다음을 말합니다.

R ≝ Production Rules of CFG
(x,y,"LBL") is a labeled-edge between x and y with “LBL” as a label 
∀r∊R: r= (A,aⱰ) ( A∊V ⋀ a∊T ∧ Ɒ∊V*) add (q,q,"a,A/Ɒ") to E
Add (q,q,"ε,z/Sz′") to E
Add (q,f,"ε,z′/z′") to E

.

우리가 그것에 대해 s-grammar를 제공 할 수없는 DCFL이있는 경우, 제발 내가 틀렸다면 제발 나를 바로 잡고 나를 바로 잡으십시오.

감사합니다.

Answer 1

실제로는 받아 들여지지 않은 언어의 예가 전문적으로 인해 매우 간단 할 수 있습니다. $ a ^ * $ 은 s-grammar에 의해 생성되지 않습니다.

사실 S-Grammar는 $ \ varepsilon $ 을 생성 할 수 없습니다. 스택에서 $ s $ 을 제거하기 위해 적어도 하나의 생산을 적용해야하며 모든 생산은 터미널 기호를 생성합니다.

그러나 이것을 전문적으로 보게 되더라도, 우리는 두 개의 문자열을 생성 할 수 없으며, 그 중 하나는 다른 하나의 접두사입니다. 모든 비사인이 다시 작성 되었기 때문에 (스택 만 새 $ \ alpha $ 을 생성 할 수 있습니다. > $ z '$ ), 더 긴 문자열 $ \ alpha \ beta $ 을 어떻게 생성합니까? 그것은 처음에는 동일한 계산을 따라야합니다.

생성하는 PDA가 실제로 빈 스택 수락이있는 PDA이기 때문에 스택이 비어 있거나 실제로 $ z '$ 만 있음) 때문입니다. 우리는 받아 들여야합니다. 빈 스택 수용으로 PDA를 결정하는 것은 접두사가없는 언어 만 생성 할 수 있습니다. 첨가중인 문자열 마커는 대개 치료법입니다.

실시간 속성 (모든 단계마다 기호 읽기)은 더 큰 문제입니다. $ \ \ mid i, j \ g ge 1 \} \ 컵 \ {a ^ ib ^ jd ^ j \ mid i, j \ GE 1 \} $ . 그것은 DPDA가 받아 들일 수 있습니다. $ a $ 을 눌러 $ b $ 을 누릅니다. 그런 다음 $ C $ 을 읽을 때 $ b $ 의 팝업을 팝하고 $ a $ 의 $ c $ 의 " 그렇지 않으면 $ d $ 을 읽을 때 $ d $ 의 $ b $ 스택을 사용합니다. 따라서 입력을 읽지 않고 스택 기호가 팝핑되어야합니다. 실시간 PDA는 그렇게 할 수 없습니다 (그리고 s-grammar). 내가 아는 소스는 Autebert, Berstel, Boasson : atext-free 언어와 공식 언어의 핸드북에서 푸시 다운 오토 타타를 나타냅니다.

물론 PDA는 단일 상태 만 있습니다. 나는 다음을 확인해야합니다. 단일 상태 제한도 허용되는 언어가 줄어 듭니다.