Un CFG che utilizza un linguaggio NIL è decidebile?

Question

Se ho una grammatica senza contesto g in modo tale che il linguaggio di G sia zero, è decidabile?

So che la risposta è sì, ma ho problemi a dimostrarlo. Il mio primo pensiero è dire che esiste un solo stato, Q1, che è lo stato di partenza e accetta lo stato per una macchina Turing che è l'equivalente di G. Questa macchina non accetterà alcun input e si fermerà immediatamente e accetta perché ha raggiunto un accettazione stato. È una risposta accettabile, o sono lontano qui?

MODIFICARE:

Come ha detto Joel di seguito, la lingua che ho descritto accetta tutte le stringhe. Per contrastare questo, propongo una seconda macchina, g '. G 'ha 3 stati, lo stato iniziale Q1, uno stato di accettazione Q2 e uno stato di rifiuto Q3. Q1 passa a Q3 su tutti i simboli nell'alfabeto di G ', e anche Q2. Q1 ha una transizione di Epsilon a Q2. Pertanto, se esistono simboli nella stringa che viene alimentata a g ', g' rifiuterà. Se non ci sono simboli, l'unica opzione è quella di prendere la transizione di Epsilon nello stato di accettazione. Come ti sembra?

MODIFICARE:

La soluzione sopra ha dimostrato di accettare la lingua l (g ') = {""}.

Answer 1

Come hai detto, la risposta è sì. Una prova generale è il fatto che dato un CFG G Puoi facilmente (bene) costruire una TM simula derivazioni usando quella grammatica. Tuttavia, stai cercando una prova breve per la lingua vuota. (Il fatto che tu abbia un CFG in questo caso è irrilevante.)

Sei sulla strada giusta in quanto se riesci a costruire un TM che si ferma sempre per una determinata lingua L, allora L è decidabile. Tuttavia, la macchina che descrivi accetterà effettivamente ogni stringa, ovvero la lingua composta da ogni possibile stringa sull'alfabeto. Questo perché se lo stato di partenza è anche uno stato di accettazione, la macchina Turing accetterà immediatamente quando inizia. Non deve leggere l'intera stringa di input (o qualsiasi parte di essa) per accettare.

Per definire un TM che non accetta nulla, lascia che l'insieme degli stati accettanti sia vuoto. Per garantire che la macchina si fermi sempre, anche la funzione di transizione può essere vuota.