Estensione al CFG, che cos'è?

Question

Si consideri la seguente estensione alle grammatiche context-free che consente alle regole di avere sul lato sinistro, uno (o più) terminale sul lato destro del non-terminale. Cioè, le regole della forma:

A b -> ... 

Il lato destro potrebbe essere qualsiasi cosa, come nelle grammatiche context-free. In particolare, è necessario non, che alla fine il lato destro abbia esattamente lo stesso simbolo del terminale. In tal caso, questa estensione sarebbe sensibile al contesto. Ma il terminale non è solo un contesto. A volte, questo terminale è chiamato "pushback".

Chiaramente, questo non è più CFG (tipo-2). Include type-1. Ma cos'è? Hai già inserito il tipo-0?

Questa estensione particolare è consentita in Definitive Clause Grammars dcg in Prolog. (Per evitare equivoci, non considero le estensioni complete di Prolog. Vale a dire che i terminali provengono da un alfabeto finito e non sono termini arbitrari, inoltre non considero gli argomenti aggiuntivi di Prolog che sono consentiti nei DCG, che vanno anche in type- . 0 già)

---

Edit: Ecco un modo semplice per descrivere l'estensione: Aggiungere a una normativa CFG del modulo

A b -> <epsilon> 

Answer 1

rispondere alla mia domanda riguardo al DCG il formalismo di Prolog, questa estensione è ora chiamato un semicontext.Vedi N253 DIN Draft for DCGs 2014-04-08 - ISO/IEC WDTR 13211-3:2014-04-08

Dato

a1, [b] --> ... . 

a2, [b,b] --> ... . 

Il terminale-sequenza [b] è ora una semicontext, così come il terminale-sequenza [b,b].

Sarebbe la stessa sequenza terminale ora apparire alla fine della regola, avremmo un contesto:

a3, [b,b] --> ..., [b,b]. 

Quindi, "semi" significa qui "metà" - simile a un semigruppo in cui metà della algebrica proprietà di un gruppo in attesa.

Answer 2

Yup suo tipo 0 credo. Il principio per i primi 3 tipi (3, 2 e 1) è che quelli non possono eseguire la riduzione. Quelli sono solo tipi generativi.

Qui è possibile trasformare un terminale in Epsilon quindi è di tipo 0.

Answer 3

Ecco una risposta parziale:

La grammatica è all'interno di tipo 0. Un context-sensitive grammar (tipo 1) ha regole della forma wAx -> wBx dove w e x sono stringhe di terminali e non-terminali e B non è vuoto. Si noti che poiché B non è vuoto, |wAx| <= |wBx|. La grammatica ha le regole del modulo Ax -> z dove z è una stringa di terminali e non-terminali e può essere vuota e x può essere rimosso. Questo viola due principi di CSG.

Unsatisfyingly, non ho risposto due cose:

• È il lingua generato dal vostro tipo-1 di grammatica? La grammatica è di tipo 0, ma ciò non significa che la lingua non può essere di tipo 1. Ad esempio, le lingue regolari (tipo-3) possono essere descritte dai CFG (tipo-2).

• È la lingua recursive? Questo è importante dal momento che, in caso affermativo, il linguaggio è decidibile (non soffre del problema dell'arresto).

  Attualmente sto tentando una prova per il secondo punto, ma è probabilmente oltre le mie capacità.