A gramática s é poderosa o suficiente para gerar todos os DCFL possíveis?

Question

Na gramática s todas as produções são em forma de A → 𝑎𝛼 , A∈V , a∈T , 𝛼∈V*

"...e qualquer par (A, a) ocorre no máximo uma vez em P." [P.Linz, 6ª ed., pág.144]

s-gramática é inequívoca e acho (não tenho certeza) que podemos descrever todas as CFL inequívocas por s-gramática.Eu quero saber a gramática s pode descrever todos os DCFL possíveis ou não? de acordo com esta frase, acho que não podemos fazer isso, mas não tenho certeza disso:

Infelizmente, nem todos os recursos de uma linguagem de programação típica podem ser expressos por uma gramática s. [P.Linz, 6ª ed., pág.152]

mas todas as línguas descritas por uma gramática s são determinísticas.

Digo isso porque podemos fazer DPDA de 2 estados para qualquer gramática simples com esta definição:

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

se houver algum DCFL para o qual não possamos fornecer uma gramática s, mostre-me isso e corrija-me se eu estiver errado.

Obrigado.

Answer 1

Na verdade o exemplo de uma linguagem não aceita pode ser bastante simples, devido a um detalhe técnico.O idioma $a^*$ não é gerado por uma gramática s.

Na verdade, uma gramática s não pode gerar $\varepsilon$.Para remover $S$ da pilha temos que aplicar pelo menos uma produção, e qualquer produção produzirá um símbolo terminal.

Mas mesmo que vejamos isso como um detalhe técnico, não podemos gerar duas strings, uma das quais é o prefixo da outra.Se pudermos gerar uma string $\alfa$ que então é aceito porque todos os veriáveis ​​​​foram reescritos (a pilha contém apenas os novos $z'$), então como geraríamos uma string mais longa $\alfa\beta$?Deve seguir o mesmo cálculo inicialmente.

Este é o caso porque o PDA que você produz é na verdade um PDA com aceitação de pilha vazia:quando a pilha está vazia (ou na verdade só tem $z'$) devemos aceitar.É bem sabido que o PDA determinístico com aceitação de pilha vazia só pode gerar linguagens sem prefixo.Adicionar um marcador de final de string geralmente é a solução.

A propriedade de tempo real (ler um símbolo a cada passo) é um problema maior.Considere o idioma $\{ a^i b^j c^i \mid i,j \ge 1\} \cup \{ a^i b^j d^j \mid i,j \ge 1\}$.Pode ser aceito por um DPDA.empurrar $a$é, empurre $b$'s.Então, ao ler um $c$ nós estouramos o $b$e compare o $a$'areia $c$'s.Caso contrário, ao ler um $d$ nós comparamos o $d$está com o $b$está usando a pilha.Portanto, você precisa abrir símbolos de pilha sem ler a entrada.Um PDA em tempo real não pode fazer isso (e nem a gramática s).A fonte que conheço refere-se a Autebert, Berstel, Boasson:Linguagens Livres de Contexto e Autômatos Pushdown no Manual de Linguagens Formais.

É claro que o PDA possui apenas um único estado.Eu tenho que verificar:parece que também a restrição estatal única reduz as línguas aceites.