Est s-grammaire assez puissant pour générer tous les possibles DCFL?

Question

Dans s-grammaire de toutes les productions sont en forme de A → 𝑎𝛼 , A∈V , a∈T , 𝛼∈V*

"...et toute paire (A, A) se produit plus d'une fois dans P." [P.Linz, 6e ed., p.144]

s-la grammaire est ambiguë et je crois (pas sûr), nous pouvons décrire tous les sans Ambiguïté-de la LCF par s-grammaire.Je veux savoir peut s de grammaire, de décrire tous les possibles DCFL ou pas ? selon cette phrase, je pense que nous ne pouvons pas le faire, mais je ne suis pas sûr à ce sujet:

Malheureusement, pas toutes les caractéristiques d'un type de langage de programmation peut être exprimé par un s-grammaire. [P.Linz, 6e ed., p.152]

mais toutes les langues qui décrit par une grammaire est Déterministe.

Je dis cela, parce que nous pouvons fait 2-etat DPDA pour tout simples de grammaire avec cette définition:

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

si il n'y a aucune DCFL que nous ne pouvons pas fournir un s-grammaire pour cela , montrez-moi s'il vous plaît corrigez-moi si je me trompe.

Merci.

Answer 1

En fait l'exemple d'une langue qui n'est pas acceptée, peut être assez simple, en raison d'un vice de forme.La langue $a^*$ n'est pas généré par un s-grammaire.

En fait, un s-grammaire ne peut pas générer $\varepsilon$.Afin de supprimer $S$ à partir de la pile, nous avons à appliquer au moins l'un de la production, et la production sera de produire un symbole terminal.

Mais même si nous voyons cela comme un vice de forme, nous ne pouvons pas générer des deux chaînes, dont l'un est le préfixe d'un autre.Si nous pouvons générer une chaîne de caractères $\alpha$ qui puis est accepté parce que tous les veriables ont été réécrits (la pile ne contient que la nouvelle $z'$), alors comment pourrait-on générer une plus longue chaîne $\alpha\beta$?Il doit suivre le même calcul initialement.

C'est le cas parce que le PDA vous produire est en fait un PDA avec pile vide acceptation:quand la pile est vide (ou en fait seulement a $z'$), nous devons accepter.Il est bien connu que deterministice PDA avec pile vide acceptation ne peut générer prefix-free langues.Addingan de fin de chaîne marqueur est généralement le remède.

La propriété en temps réel (la lecture d'un symbole à chaque étape) est un gros problème.Considérer la langue $\{ a^i b^j c^i \mi i,j \ge 1\} \cup \{ a^i b^j j^j \mi i,j \ge 1\}$.Il peut être accepté par un DPDA.pousser $a$'s, pousser $b$s'.Puis lors de la lecture d'un $c$ nous pop la $b$'s et de comparer les $a$'s et $c$s'.Sinon lors de la lecture d'un $d$ nous comparons les $d$'s avec la $b$'s à l'aide de la pile.Ainsi, vous devez éclater de pile de symboles, sans lire les commentaires.En temps réel PDA ne peut pas le faire (et ni le s-grammaire).La source je sais que cela se réfère à Autebert, Berstel, Boasson:Libre de tout contexte de Langues et de Refoulement des Automates dans le Manuel de Langages Formels.

Bien sûr, le PDA n'a qu'un seul état.Je dois vérifier:il semble également que la seule restriction de l'etat réduit les langues acceptées.