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

DPDA for any s-grammar

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.


  • 1
    $\begingroup$ Please don't cross-post on multiple sites simultaneously. Thank you. $\endgroup$
    – D.W.
    Commented Jun 13, 2020 at 21:44

1 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.