¿Es lo suficientemente poderoso de S-Grammar para generar todos los DCFL posibles?

Question

en S-gramática Todas las producciones están en forma de A → 𝑎𝛼 , A∈V , a∈T , 𝛼∈V*

"... y cualquier par (a, a) ocurre a lo sumo una vez en P." [p. Linz, 6ª ed. , pag. 144]

s-gramática es inequívoco y creo (no estoy seguro) Podemos describir a todos los CFL no ambiguos por S-Grammar. Quiero saber can s-gramática describir todo DCFL posibles o no? Según esta oración, creo que no podemos hacerlo, pero no estoy seguro de eso:

Desafortunadamente, no todas las características de un lenguaje de programación típico pueden expresarse por una gramática S. [p. Linz, 6ª ed. , pag. 152]

pero todos los idiomas que describidos por una gramática S son deterministas .

Digo esto, porque podemos hacer DPDA de 2 estados para cualquier gramática simple con esta definición:

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 hay algún DCFL que no podamos proporcionar una gramática S, mostrarme que por favor y corríjame si estoy equivocado.

gracias.

Answer 1

En realidad, el ejemplo de un idioma no aceptado puede ser bastante simple, debido a un tecnicismo. El idioma $ a ^ * $ no es generado por una gramática S.

De hecho, una gramática S puede generar $ \ varepsilon $ . Para eliminar $ s $ de la pila, tenemos que aplicar al menos una producción, y cualquier producción producirá un símbolo terminal.

Pero incluso si vemos esto como un tecnicismo, no podemos generar dos cadenas, una de las cuales es el prefijo de otro. Si podemos generar una cadena $ \ alfa $ que luego se acepta porque todas las verificaciones han sido reescritas (la pila solo contiene el nuevo $ z '$ ), entonces, ¿cómo generamos una cadena más larga $ \ alfa \ beta $ ? Debe seguir inicialmente el mismo cálculo.

Este es el caso porque la PDA que produce es en realidad una PDA con la aceptación de la pila vacía: cuando la pila está vacía (o en realidad solo tiene $ z '$ ) Debemos aceptar. Es bien sabido que el determinista PDA con la aceptación de la pila vacía solo puede generar lenguajes sin prefijo. El marcador de fin de cadena de adición suele ser el remedio.

La propiedad en tiempo real (leyendo un símbolo en cada paso) es un problema mayor. Considere el idioma $ \ {a ^ ^ ^ a mediados i, j \ ge 1 \} \ cucas \ {a ^ ^ \ ^ jd ^ j \ mid i, j \ GE 1 \} $ . Puede ser aceptado por un DPDA. PUSH $ A $ 's, Push $ b $ ' s. Luego, cuando lee un $ C $ Pop the $ b $ 's y compare la $ A $ 's y $ C $ ' s. De lo contrario, al leer un $ d $ comparamos el $ d $ 's con el $ b $ 's usando la pila. Por lo tanto, necesita estallar los símbolos de la pila sin leer la entrada. Una PDA en tiempo real no puede hacer eso (y ni la gramática S). La fuente que sé para esto se refiere a AUTBERT, BERSTEL, BOASSON: lenguas libres de contexto y autómatas de empuje en el manual de idiomas formales.

Por supuesto, el PDA tiene solo un solo estado. Tengo que verificar: Parece que también la restricción del estado individual reduce los idiomas aceptados.