È corretto: se una grammatica di tipo 3 genera $ \ Sigma ^ * $ non è c.e

Question

Un esempio dal libro di Sipser, introduzione alla teoria del calcolo, mostra che non è decidabile per una $ TM $ per riconoscere se una classe $ cfg $ (o una grammatica di tipo 2) Genera $ \ sigma ^ * $ , dove $ \ Sigma $ è l'alfabeto. Chiama questa lingua $ cfg_ {all} $

Ma anche la lingua sopra non è elaborabile. Ci può essere una riduzione da $ cfg_ {all} $ a $ \ bar {a_ {tm}} $ , dove $ \ bar {a_ {tm}} $ è la lingua st L'ingresso $ TM $ non accetta alcun input. $ \ bar {A_ {tm}} $ non è elaborabilmente enumerabile.

Ma potremmo dire che se una grammatica di tipo 3 genera o meno genera $ \ sigma ^ * $ non è anche c.e. ? (Poiché i grammatiche di tipo 3 sono un sottoinsieme di grammatiche senza contesto). Mentre è vero che un Automaton finito può riconoscere $ \ sigma ^ * $ , questa lingua è diversa dal punto di vista se una grammatica di tipo 3 genera $ \ Sigma ^ * $ ?

Solo per chiarire la fonte della mia confusione, in sintesi, è decidabile per una $ TM $ per decidere se un Automaton Pushdown riconosce $ \ Sigma ^ * $ o accetta qualsiasi input, ma non è decidabile o addirittura computabile per un $ TM $ per riconoscerlo Un CFG genera $ \ Sigma ^ * $ . Allo stesso modo, è decidabile per una $ TM $ per verificare se un Automaton finito accetta $ \ Sigma ^ * $ , ma potrebbe non essere decidabile per una $ TM $ per verificare se una grammatica tipo 3 genera $ \ Sigma ^ * $ . È in qualche modo la differenza tra il riconoscimento e la generazione.

Modifica: apparentemente per un automa automatico di Pushdown per riconoscere $ \ sigma ^ * $ non è decidabile

Answer 1

Per vedere se una grammatica di tipo 3 (regolare) genera $ \ sigma ^ * $ basta costruire la DFA minima che accetta la lingua e controlla se è solo iniziale= Stato finale, con loop su tutti i simboli.Tutte le costruzioni coinvolte sono efficaci.