Is s-grammar powerful enough to generate all possible DCFL?

Question

In s-grammar all productions are in form of A → 𝑎𝛼 , A∈V , a∈T , 𝛼∈V*

"... and any pair (A, a) occurs at most once in P." [P. Linz, 6th ed. , p. 144]

s-grammar is Unambiguous and i think (not sure) we can describe all Unambiguous-CFL by s-grammar. I want to know can s-grammar describe all possible DCFL or not ? according to this sentence, I think we can't do it but i'm not sure about that:

Unfortunately, not all features of a typical programming language can be expressed by an s-grammar. [P. Linz, 6th ed. , p. 152]

but all languages which described by an s-grammar is Deterministic.

I say this, because we can made 2-state DPDA for any simple-grammar with this definition:

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

if there is any DCFL that we can not provide an s-grammar for it , show me that please and correct me if i'm wrong.

Thanks.

Answer 1

Actually the example of a language not accepted can be quite simple, due to a technicality. The language $a^*$ is not generated by a s-grammar.

In fact, an s-grammar cannot generate $\varepsilon$. In order to remove $S$ from the stack we have to apply at least one production, and any production will produce a terminal symbol.

But even if we see this as a technicality, we cannot generate two strings, one of which is the prefix of another. If we can generate a string $\alpha$ which then is accepted because all veriables have been rewritten (the stack only contains the new $z'$), then how would we generate a longer string $\alpha\beta$? It must follow the same computation initially.

This is the case because the PDA you produce is actually a PDA with empty stack acceptance: when the stack is empty (or actually only has $z'$) we must accept. It is well known that deterministice PDA with empty stack acceptance can only generate prefix-free languages. Addingan end-of-string marker is usually the remedy.

The real-time property (reading a symbol every step) is a larger problem. Consider the language $\{ a^i b^j c^i \mid i,j \ge 1\} \cup \{ a^i b^j d^j \mid i,j \ge 1\}$. It can be accepted by a DPDA. push $a$'s, push $b$'s. Then when reading a $c$ we pop the $b$'s and compare the $a$'s and $c$'s. Otherwise when reading a $d$ we compare the $d$'s with the $b$'s using the stack. Thus you need popping of stack symbols without reading input. A real-time PDA cannot do that (and neither the s-grammar). The source I know for this refers to Autebert, Berstel, Boasson: Context-Free Languages and Pushdown Automata in the Handbook of Formal Languages.

Of course the PDA has only a single state. I do have to check: it seems that also the single state restriction reduces the languages accepted.