Come determinare se una lingua è ricorsiva o enumerabile in modo ricorsivo?

Question

Devo determinare se una lingua (ad esempio L = {a^nb^mc^s | 0 < = n < = m < = s}) è regolare, senza contesto, ricorsiva, ricorsiva enumerabile o nessuna di esse .

So come determinare se una lingua è regolare (trova un DFA o un'espressione regolare che funziona) o privo di contesto (trova un PDA o una grammatica context-free che funzioni); So che un linguaggio ricorsivo ha una macchina di Turing che si arresta sempre e che un linguaggio ricorsivamente enumerabile ha una macchina di Turing che non può fermarsi.

Quindi la domanda è: esiste un criterio veloce per determinare se la lingua è ricorsiva o ricorsivamente enumerabile o nessuno dei due? Per esempio, non devo costruire un PDA per capire che un linguaggio è privo di contesto, non posso vederlo dal fatto che richiede uno stack; c'è un simile approccio veloce al problema (che si spera risparmi il problema di costruire una macchina di Turing)?

Answer 1

Non esiste un modo strutturale per verificare se una lingua è ricorsiva o enumerabile in modo ricorsivo. C'è in realtà una prova davvero interessante che dice che per ogni automa capace di riconoscere i linguaggi ricorsivi, c'è almeno un linguaggio RE non in R che l'automa accetta anche; è una variante dell'argomento di diagonalizzazione che usi per mostrare l'esistenza di problemi indecidibili.

Il modo principale in cui si dimostra che una lingua è in RE ma non R è di dimostrare che la lingua è in RE (forse definendo una TM per esso), quindi di ridurre un problema noto in RE ma non R in quello problema. Ad esempio, se puoi dimostrare che qualsiasi istanza del problema di interruzione può essere risolta trasformandola in un'istanza del tuo problema, sai che non può avere una soluzione ricorsiva e se la segui con una TM per il lingua sai che la lingua è in RE. Insieme, hai una lingua in RE ma non R.

Answer 2

Per il linguaggio senza contesto un metodo rapido è solo vedere il numero di comparazioni.
Nell'esempio, vedere n<=m e m<=s. Quindi ci sono due confronti coinvolti. Quindi puoi toglierlo semplicemente dicendo che non è privo di contesto. Se è coinvolto un singolo confronto, chiamalo come un linguaggio privo di contesto.

Lo stesso è il caso delle lingue regolari. Non ci dovrebbe essere alcuna relazione tra le due variabili, voglio dire che non ci deve essere alcun tipo di confronto. Ad esempio, prendi in considerazione le lingue: 0^m+n 1^n 0^m. Guardate attentamente che c'è un solo confronto fatto che è m+n = n+m (premendo e scoppiando i simboli) Quindi è privo di contesto.
Ora vedere 0^n+m 1^n+m 0^m vedere chiaramente il confronto tra il primo 2 e il successivo.

Mi sono preso un po 'di tempo per capirlo. Ma ci vorrà un po 'per prendere le decisioni. Credimi funziona davvero. Ecco l'ultimo esempio per la lingua normale. a^n b^2m è regolare (Vedi non ci sono confronti tra n e m) ed è {a^n b^m |n=2m} contesto libero in quanto ha un solo confronto (non regolare)

Spero che questo aiuti