S-grammar是否足够强大，可以生成所有可能的dcfl？

Question

在S-grammar中，所有制作的都是A → 𝑎𝛼 , A∈V , a∈T , 𝛼∈V*

的形式

“......以及任何对（a，a）最多一次发生在p.” [p。林茨，第6届。 ，p。 144]

s-grammar是明确的，我想（不确定）我们可以通过s-grammar描述所有明确的cfl。我想知道可以s-grammar描述所有可能的dcfl还是不是？根据这句话，我想我们不能这样做，但我不确定：

不幸的是，并非典型编程语言的所有功能都可以由S-Grammar表示。 [p。林茨，第6届。 ，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

.

如果有任何DCFL，我们不能为它提供S-grammar，请告诉我，如果我错了，请纠正我。

谢谢。

Answer 1

实际上，由于技术性，尚未接受的语言的示例可以很简单。语言 $ a ^ * $ 不是由s-grammar生成的。

事实上，S-Grammar无法生成 $ \ varepsilon $ 。为了从堆栈中删除 $ s $ ，我们必须申请至少一个生产，并且任何生产都会产生终端符号。

但即使我们认为这是一种技术性，我们也无法生成两个字符串，其中一个是另一个的前缀。如果我们可以生成字符串 $ \ alpha $ 然后被接受，因为所有验证都已重写（堆栈仅包含新 $ z'$ ），那么我们将如何生成更长的字符串 $ \ alpha \ beta $ ？它必须最初遵循相同的计算。

这是这种情况，因为您生成的PDA实际上是一个具有空堆栈验收的PDA：当堆栈为空时（或实际上只有 $ z'$ ）我们必须接受。众所周知，具有空堆栈验收的确定性PDA只能生成无前缀语言。 addingan末尾标记通常是补救措施。

实时属性（每步读取符号）是一个更大的问题。 考虑语言 $ \ {a ^ ib ^ jc ^ i \ mid i，j \ ge 1 \} \ cup \ {a ^ ib ^ jd ^ j \ mid i，j \ GE 1 \} $ 。它可以被DPDA接受。推送 $ a $ ，推送 $ b $ 。然后在读取 $ c $ 我们弹出 $ b $ s并比较 $ a $ 's和 $ c $ 。否则在读取<跨度类=“math-container”> $ d $ 时，我们将使用 $ d $ 。数学集装箱“> $ B $ 使用堆栈。因此，您需要在不读取输入的情况下弹出堆栈符号。实时PDA不能做到这一点（既不是S-GRAMMAR）。我所知道的来源是指Autebert，Berstel，Boasson：正式语言手册中的无背景语言和推动自动机。

当然，PDA只有一个状态。我不得不检查：似乎也是单一国家限制也减少了所接受的语言。