Este é correto: se uma gramática tipo 3 gera ou não $ \ sigma ^ * $ não é c.e

Question

Um exemplo do livro da extremidade, introdução à teoria do cálculo, mostra que não é decível para uma $ tm $ reconhecer se uma $ cfg $ (ou uma gramática tipo 2) gera $ \ sigma ^ * $ , onde $ \ Sigma $ é o alfabeto. Chame esta linguagem $ cfg_ {tudo} $

Mas a linguagem acima também não é compilável. Pode haver uma redução de $ cfg_ {tudo} $ para $ \ bar {a_ {tm}} $ , onde $ \ bar {a_ {tm}} $ é o idioma st A entrada $ tm $ não aceita nenhuma entrada. $ \ bar {a_ {tm}} $ não é computableamente enumerável.

Mas poderíamos dizer que se uma gramática tipo 3 gera ou não $ \ sigma ^ * $ também não é c.e. ? (Como as gramáticas do tipo 3 são um subconjunto de gramáticas sem contexto). Embora seja verdade que um autômato finito pode reconhecer $ \ sigma ^ * $ <$ <$ <\ $>, esta linguagem é diferente do direito de uma gramática do tipo 3 gera matemática $ \ sigma ^ * $ ?

Apenas esclarecer a fonte da minha confusão, em resumo, é decapável para uma $ tm $ para decidir se um autômato de pushdown reconhece $ \ sigma ^ * $ ou aceita qualquer entrada, mas não é decidível ou mesmo computableamente enumerável para uma $ tm $ para reconhecer que Um CFG gera $ \ sigma ^ * $ . Da mesma forma, é decapável para uma $ tm $ para verificar se um autômato finito aceita $ \ sigma ^ * $ , mas pode não ser decidível para uma $ tm $ para verificar se uma gramática tipo 3 gera $ \ sigma ^ * $ . É de alguma forma a diferença entre reconhecer e gerar.

Editar: Aparentemente para um autômato Pushdown para reconhecer $ \ sigma ^ * $ não é decidível

Answer 1

Para ver se uma gramática tipo 3 (regular) gera $ \ sigma ^ * $ <$ apenas construa o DFA mínimo aceitando o idioma e verifique se é apenas inicial= estado final, com loop em todos os símbolos.Todas as construções envolvidas são eficazes.