S-Grammar è abbastanza potente da generare tutto il possibile DCFL?

Question

In S-Grammar Tutte le produzioni sono in forma di A → 𝑎𝛼 , A∈V , a∈T , 𝛼∈V*

.

"... e qualsiasi coppia (A, A) si verifica al massimo una volta in P." [p. Linz, 6 ° ed. , p. 144]

S-Grammar è inequivocabile e penso (non sono sicuro) possiamo descrivere tutto Unambligue-CFL da S-Grammart. Voglio sapere Can S-Grammar Descrivi tutto il possibile DCFL o no? Secondo questa frase, penso che non possiamo farlo ma non ne sono sicuro:

.

Sfortunatamente, non tutte le funzionalità di un tipico linguaggio di programmazione possono essere espresse da una grammatica S. [p. Linz, 6 ° ed. , p. 152]

Ma Tutte le lingue descritte da una grammatica S è deterministica .

Dico questo, perché possiamo fare DPDA a 2 stati per qualsiasi semplice grammatica con questa definizione:

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 c'è un DCFL che non possiamo fornire una grammatica S, mostrami che per favore e correggimi se sbaglio.

Grazie.

Answer 1

In realtà l'esempio di una lingua non accettata può essere abbastanza semplice, a causa di un tecnico. La lingua $ a ^ * $ non è generato da una grammatica S.

In effetti, una grammatica S non può generare $ \ varepsilon $ . Per rimuovere $ s $ Dalla pila dobbiamo applicare almeno una produzione e qualsiasi produzione produrrà un simbolo terminale.

Ma anche se lo vediamo come tecnicità, non possiamo generare due stringhe, una delle quali è il prefisso di un altro. Se possiamo generare una stringa $ \ alfa $ che quindi è accettato perché tutte le variabili sono state riscritte (lo stack contiene solo la nuova $ z '$ ), quindi come genereremmo una stringa più lunga $ \ alfa \ beta $ ? Deve seguire lo stesso calcolo inizialmente.

Questo è il caso perché il PDA che produci è in realtà un PDA con accettazione da stack vuota: quando lo stack è vuoto (o in realtà ha solo $ z '$ ) Dobbiamo accettare. È noto che il determinista PDA con l'accettazione della pila vuota può generare solo lingue senza prefissione. Il marker di fine stringa aggiuntivo è solitamente il rimedio.

La proprietà in tempo reale (leggendo un simbolo ogni passaggio) è un problema più grande. Considera la lingua $ \ {a ^ ib ^ jc ^ i \ metà i, j \ ge 1 \} \ \ cup \ {a ^ ib ^ jd ^ j \ metà i, j \ Ge 1 \} $ . Può essere accettato da un DPDA. premere $ a $ 's, push $ B $ ' s. Quindi quando si legge una classe $ c $ POP la $ B $ 's e confronta la $ A $ 's e $ c $ ' s. Altrimenti quando si legge una classe $ D $ Confrontiamo la $ d $ 's con la $ B $ Usando lo stack. Quindi è necessario schioccare i simboli dello stack senza leggere input. Un PDA in tempo reale non può farlo (e né la grammatica S). La fonte che conosco per questo si riferisce a AUTEBERT, BETERSEL, Boasson: lingue senza contesto e automobili di spingolazione nel manuale delle lingue formali.

Ovviamente il PDA ha solo un singolo stato. Devo controllare: sembra che anche la restrizione dello stato singolo riduce le lingue accettate.