Diferença entre regular de gramática e CFG na geração de computação histórias e $\Sigma^*$

Question

Eu gostaria de perguntar para a intuição para entender a diferença entre um CFG geração $\Sigma^*$ e uma gramática regular de geração de $\Sigma^*$..Eu tenho os exemplos aqui de Sipser.Deixe $ALL_{CFG}$ consulte a linguagem de um determinado CFG gera $\Sigma^*$, e deixe $ALL_{REX}$ consulte o idioma que uma dada expressão regular gera $\Sigma^*$ (e uma vez que para cada expressão regular não regular de gramática, podemos dizer também que o equivalente a regular a gramática gera $\Sigma^*$).

A partir do que eu tenho, nós temos:

• $ALL_{CFG}$ não é decidível, também não é Turing-reconhecível.Deixe $\overline{A_{TM}}$ consulte o idioma que uma TM $M$ não aceitar a palavra de entrada $w$.Podemos reduzir $\overline{A_{TM}}$ para $ALL_{CFG}$ em tempo polinomial usando computação histórias.A redução constrói uma CFG, que gera todas as palavras possíveis, onde:1) a primeira personagens não correspondem $w$, 2) a última caracteres não correspondem aceitar as configurações, e 3) caracteres não correspondem válido transições de $M$'s configurações.Assim, $A_{TM}$ não aceita $w$ iff CFG gera $\Sigma^*$ (i.é.não há aceitar computação histórias).Desde a redução mapas $\overline{A_{TM}}$ para $ALL_{CFG}$, e $\overline{A_{TM}}$ não é Turing-reconhecível, $ALL_{CFG}$ não é Turing-reconhecível.

• $ALL_{REX}$ é decidível, pois é decidível se um autômato finito aceita $\Sigma^*$.No entanto, a aceitação problema para qualquer idioma $R$ pode ser polinominalmente reduzido para a língua $ALL_{REX} - f(R_M)$, onde $R_M$ é um TM que decide $R$, e $f(R_M)$ é uma redução similar da computação histórias como descrito acima.Em mais detalhe, $f(R_M)$ regular a gramática que gera todas as palavras possíveis que 1) os primeiros caracteres não correspondem $w$, 2) a última caracteres não correspondem a rejeição de configurações, e 3) caracteres não correspondem válido transições de $R_M$'s configurações.O jogo decisivo para $ALL_{REX} - f(R_M)$ verifica se está vazio, o que significa que $f(R_M)$ é igual a $\Sigma^*$).Se estiver vazio, então não há rejeição de computação histórias e $w \em R$.(Em Sipser, ele usou algo como isso para mostrar EXPSPACE-completude para $ALL_{REX} - f(R_M)$)

Eu gostaria de perguntar:

A partir de cima, tanto regulares, gramáticas e CFG poderia gerar computação histórias de um TM, e ambos poderiam gerar $\Sigma^*$.Mas o que é com o poder fundamental do CFG da gramática que torna válida para reduzir $\overline{A_{TM}}$ para $ALL_{CFG}$, mas não é possível que $\overline{A_{TM}}$ para ser reduzido para $ALL_{REX} - f(A_{TM})$ ?Eu sei que nós não podemos reduzir a $\overline{A_{TM}}$ para $ALL_{REX} - f(A_{TM})$ desde $ALL_{REX} - f(A_{TM})$ é decidível, enquanto $\overline{A_{TM}}$ não é Turing-reconhecível...Mas eu gostaria de entender isso em termos de diferença na geração de energia entre CFG e regulares, gramáticas, através de suas regras.

Por exemplo, a partir do que eu li, CFG de permitir as regras $A ightarrow A.C.$, onde $B$ e $C$ são cadeias de variáveis e terminais.Por outro lado, regulares gramáticas permitir apenas que as regras na forma de $A ightarrow aB$, onde $a$ é um terminal.Eu gostaria de perguntar:por que não incorporar regras do formulário $A ightarrow A.C.$ para uma gramática, dar-lhe o suficiente geração de energia, que ele já é válida para reduzir $\overline{A_{TM}}$ para a gramática (i.e.para o CFG).

Answer 1

O resumo da prova de undecidability não é preciso.Sua especificação de $\overline{A_{TM}}$ não é correto.

Para um razoável exposição a prova, ver https://liacs.leidenuniv.nl/~hoogeboomhj/segunda/codingcomputations.pdf particularmente início da Seção 1 e Seção 3.

A intuição não é fácil transmitir, como a prova não é totalmente trivial.Mas aqui é o núcleo do fato.Deixe $v de$w ser duas configurações de uma máquina de Turing.Escrever $n(v)$ para ser a próxima configuração da máquina de Turing depois de um único passo de cálculo, se você iniciar a configuração $v$.Definir o idioma

$$L = \{v \# w^R \meados de n(v) e w\}.$$

Em seguida, a tecla fato é que $L$ é livre de contexto.Isso leva alguns a prova;provando que é um passo fundamental para a prova.No entanto, essa é a resposta para a sua pergunta: $L$ é livre de contexto, mas não normais.Como resultado, pode-se reduzir a interrupção problema $ALL_{CFG}$ mas não para $ALL_{REX}$.

Eu ter pulado muitos passos para dar a você uma visão geral da idéia principal.Você vai precisar para ler a prova para preencher os detalhes.Eu sugiro que você próximo de ler e entender a prova, com esta perspectiva em mente, e, em seguida, rever o que eu escrevi aqui.Espero que ajudará você a compreender por que a prova válida para o contexto livre de idiomas, mas iria conseguir regular de idiomas.

Answer 2

A diferença entre os modelos de hastes, de forma intuitiva, a partir da capacidade de CFGs contagem.Mais precisamente, CFGs são capazes de gerar seqüências de caracteres do formulário $a^nb^n$, onde o número de $a$'s e $b$'s é o mesmo.

Esta habilidade concede o poder para comparar seqüências de caracteres, que pode então ser utilizada para mostrar undecidability, porque o CFG é capaz de comparar o conteúdo de uma fita entre dois períodos consecutivos de configurações.

Isso se torna um pouco mais evidente se se lembrar que a interrupção problema para dois-contador de máquinas (Minsky máquinas) é indecidíveis.Lá, uma configuração é dada pelos valores de dois contadores.Você pode deste como TM com uma espécie de unários alfabeto (embora não exatamente).Em dois contra máquinas, comparando dois períodos consecutivos de configurações exatamente quantidades de comparar os valores dos contadores em etapas consecutivas, o que é certo até o beco para CFGs.

Em contraste, línguas comuns são capturados pelos estados finitos autômatos, que são finitos de memória, e é capaz de contar apenas com um número fixo.Assim, estes autómatos pode simular um TM, desde que o comprimento de uma configuração é limitado antecipadamente.Por que isto nos dar PSPACE dureza?Bem, você pode simular qualquer TM que funciona em espaço limitado, ele não tem que ser polinomial na entrada.No entanto, para que a própria redução a ser polinomial, você precisa de dependente para ser polinomial.Assim, você obtém exatamente PSPACE dureza.

Com relação ao "tipo" de regras, não é tanto o $A\BC para$ regras que são um problema, é mais nas regras do formulário $A\a aAb$ (ou, mais geralmente, a capacidade de ter cíclica as regras).A razão é que $A\BC para$ tem uma estrutura em "árvore", e se $B$ e $C$ não são relacionadas mais tarde, então esta é efetivamente uma operação de união, a qual regular de idiomas pode simular.

No entanto, uma regra do formulário $A\a aAb$ mantém o "contexto" $A$, o que é algo regular de idiomas não pode fazer.

Para resumir:

Semanticamente, o poder de CFGs reside na sua capacidade de contar.

Sintaticamente, o poder de CFGs reside no cíclica regras.