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

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


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.

• Please don't cross-post on multiple sites simultaneously. Thank you.
– D.W.
Jun 13 '20 at 21:44

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.