Differenza tra grammatica regolari e CFG nella generazione di storie di calcolo e $ \ sigma ^ * $ $

Question

Vorrei chiedere l'intuizione di comprendere la differenza tra un cfg generazione di $ \ sigma ^ * $ e una grammatica regolare che genera $ \ Sigma ^ * $ .. Ho ottenuto gli esempi qui da Sipser. Let $ ALL_ {CFG} $ Fare riferimento alla lingua che un determinato CFG genera $ \ Sigma ^ * $ e Let $ ALL_ {rex} $ Fare riferimento alla lingua che una determinata espressione regolare genera $ \ Sigma ^ * $ < / span> (e poiché per ogni espressione regolare c'è una grammatica regolare, possiamo anche dire che la grammatica regolare equivalente genera $ \ sigma ^ * $ ). .

Da quello che ho ottenuto, abbiamo:

.

.

• $ ALL_ {CFG} $ non è decidabile, non è anche in giudizio-riconoscibile. Let $ \ Overline {A_ {TM}} $ Fare riferimento alla lingua che un TM $ M $ Non accettare la parola di input $ W $ . Possiamo ridurre $ \ overline {a_ {tm}} $ a $ ALL_ {CFG} $ in polinomiale tempo che utilizza storie di calcolo. La riduzione costruisce un CFG che genera tutte le parole possibili in cui: 1) i primi caratteri non corrispondono a $ W $ , 2) Gli ultimi caratteri non corrispondono ad accettare le configurazioni e 3) I caratteri non corrispondono alle transizioni valide della $ M $ Configurazioni. Quindi, $ A_ {TM} $ non accetta $ W $ IFF Il CFG genera $ \ Sigma ^ * $ (cioè non ci sono storie di calcolo accettate). Dal momento che le mappe di riduzione $ \ overline {a_ {tm}} $ a $ ALL_ {CFG} $ , e $ \ Overline {A_ {TM}} $ non è la Turing-riconoscibile, $ ALL_ {CFG} $ non è tenuto-riconoscibile.

• $ ALL_ {REX} $ è decidabile poiché è decidabile se un Automaton finito accetta $ \ Sigma ^ * $ . Tuttavia, il problema di accettazione per qualsiasi linguaggio normale $ R $ può essere ridotto polinomiamente alla lingua $ ALL_ {REX} - F (R_m) $ , dove $ r_m $ è un TM che decide $ r $ , e $ f (r_m) $ è una riduzione simile delle storie di calcolo come sopra descritta. Più in dettaglio, $ f (r_m) $ è la grammatica regolare che genera tutte le parole possibili dove 1) i primi caratteri non corrispondono a $ W $ , 2) Gli ultimi caratteri non corrispondono alle configurazioni di rifiuto e 3) I caratteri non corrispondono alle transizioni valide della $ r_m $ configurazioni. The Decider for $ ALL_ {REX} - f (r_m) $ controlli se è vuoto (il che significa che $ f ( R_m) $ è uguale a $ \ sigma ^ * $ ). Se vuoto, quindi non ci sono storie di calcolo di rifiuto e $ w \ in r $ . (A Sipser, ha usato qualcosa come questo per mostrare Expspace-completezza per $ all_ {rex} - f (r_m) $ )

Vorrei chiedere:

.

Dall'alto, sia grammatiche regolari che CFG potrebbero generare storie di calcolo di un TM, ed entrambi potrebbero generare $ \ sigma ^ * $ . Ma cos'è con il potere fondamentale della grammatica della CFG che rende valido per ridurre $ \ overline {A_ {tm}} $ a $ ALL_ {CFG} $ , ma non è possibile per $ \ Overline {A_ {TM}} $ per essere ridotto a $ ALL_ {REX} - F (A_ {TM}) $ ? So che non possiamo ridurre $ \ Overline {A_ {TM}} $ a $ ALL_ {REX} - F (A_ {Tm}) $ poiché $ ALL_ {REX} - F (A_ {TM}) $ è decidabile, mentre $ \ Overline {A_ {TM}} $ non è in forma-riconoscibile ... ma vorrei capirlo in termini di differenza di generare il potere tra le cfg e le grammatiche regolari attraverso le loro regole. .

Ad esempio, da quello che ho letto, il CFG consente alle regole $ a \ raggi BC $ , dove $ B $ B e $ c $ sono stringhe di variabili e terminali. D'altra parte, le grammatiche regolari consentono solo le regole sotto forma di

-Container "> $ A \ Randerarow AB $ , dove $ A $ è un terminale. Vorrei chiedere: perché incorpora le regole della forma $ A \ RightArrow BC $ a una grammatica, dargli abbastanza generare potenza in modo tale che sia già valido per ridurre $ \ Overline{A_ {TM}} $ ALLA GRAMMAMAR (cioè al CFG).

Answer 1

Il tuo riassunto della prova di indecisionebilità non è accurato. Le specifiche di $ \ Overline {A_ {TM}} $ non è corretto.

Per una ragionevole esposizione della prova, vedere https://liacs.leidenuniv .nl / ~ hoogeboomhj / second / codingComputations.pdf in particolare l'inizio della sezione 1 e la sezione 3.

L'intuizione non è facile da trasmettere, poiché la dimostrazione non è interamente banalizzata. Ma qui è il fatto principale. Let $ V, W $ Essere due configurazioni di una macchina di Turing. Scrivi $ N (V) $ Per essere la prossima configurazione della macchina di Turing dopo una singola fase del calcolo, se si avvia alla configurazione $ V $ . Definisci la lingua

$$ l={v \ # w ^ r \ metà n (v) \ ne w \}. $$

Quindi il fatto chiave è che $ l $ è privo di contesto. Questo prende una certa prova; dimostrando che è un passo chiave nella prova. Tuttavia, questa è la risposta alla tua domanda: $ l $ è privo di contesto ma non regolare. Di conseguenza, possiamo ridurre il problema di fermezza a $ ALL_ {CFG} $ ma non a $ ALL_ {REX} $ .

Ho saltato molti passaggi per darti una panoramica dell'idea principale. Avrai bisogno di leggere la prova piena per compilare i dettagli. Ti suggerisco di leggere e capire la prova, con questa prospettiva in mente, e poi rivisita ciò che ho scritto qui. Speriamo che ti aiuterà a capire perché la prova detiene per le lingue senza contesto, ma non avrebbe fallito per le lingue regolari.

Answer 2

La differenza tra i modelli steli, intuitivamente, dalla capacità di CFG di conteggio . Più precisamente, i CFG sono in grado di generare stringhe del modulo $ a ^ nb ^ n $ , dove il numero di $ a $ 's e $ B $ ' s è lo stesso.

Questa abilità garantisce il potere di confrontare le stringhe, che possono quindi essere utilizzate per mostrare l'indecidibilità, poiché il CFG è in grado di confrontare il contenuto di un nastro tra due configurazioni consecutive.

Questo diventa un po 'più evidente se si ricorda che il problema di arresto per due contatore (Minsky Machines) è indecidabile. Lì, una configurazione è data dai valori di due contatori. Puoi questo di questo come TM con una sorta di alfabeto universale (anche se non esattamente). In due controtrici, confrontando due configurazioni consecutive equivale esattamente a confrontare i valori dei contatori in passaggi consecutivi, che è proprio il vicolo per CFG.

A contrasto, le lingue regolari vengono catturate da Automati di stato finiti, che hanno una memoria finita e sono in grado di contare solo fino a un numero fisso. Pertanto, questi automi possono simulare un TM finché la lunghezza di una configurazione è delimitata in anticipo. Perché questo ci dà la durezza PSPACE? Bene, puoi simulare qualsiasi TM che funziona nello spazio limitato, non deve essere polinomiale nell'input. Tuttavia, affinché la riduzione stessa sia polinomiale, è necessario il destinato a essere polinomiale. Quindi, ottieni esattamente la durezza PSPACE.

Per quanto riguarda il "tipo" delle regole, non è così tanto la $ A \ a BC $ regole che sono un problema, è più nelle regole del Forma $ A \ a AAB $ (o più in generale, la capacità di avere ciclico regole). Il motivo è che $ A \ a BC $ ha una struttura "albero" e se $ B $ e $ c $ non è correlato in seguito, quindi questo è efficacemente un'operazione dell'Unione, che le lingue regolari possono simulare.

Tuttavia, una regola del modulo $ a \ a AAB $ mantiene il "contesto" $ A $ , che è qualcosa che le lingue regolari non possono fare.

Per riassumere:

.

Semanticamente, il potere dei CFG è nella loro capacità di contare.

sintatticamente, la potenza dei CFG è in regole cicliche.