Por que decidir a regularidade de uma linguagem sem contexto é indecidível?

Como estudei, decidir a regularidade das linguagens sem contexto é indecidível.

No entanto, podemos testar a regularidade usando o teorema de Myhill-Nerode, que fornece uma condição necessária e suficiente. Portanto, o problema deve ser decidido.

Onde está meu erro?

formal-languages computability regular-languages undecidability Jiya
fonte

Como você propõe saber se a relação Myhill-Nerode possui um número finito de classes de equivalência? Que propriedade das linguagens livres de contexto você acha que permite fazer isso?

precisa saber é o seguinte

Verifique a definição de computabilidade: você precisa fornecer uma máquina de Turing (ou, mais geralmente, um algoritmo) que resolva o problema (sempre). Myhill-Nerode não é, por si só, um algoritmo, apenas uma caracterização. A propriedade fornecida é decidível? Você já tentou transformar o teorema em um algoritmo desse tipo?

Raphael

@Jiya O que você quer dizer com "decidir regularidade"? A princípio, parece óbvio o que isso significa, mas na verdade é mais sutil. Um procedimento de decisão (algoritmo) deve receber uma entrada finita; então, como você daria uma linguagem infinita como entrada? Talvez você queira usar expressões como

{a^{n} b^{n} ∣ n \geq 0}

$\{a^nb^n\mid n\ge 0\}$ . OK, mas que expressões você permitirá?

{a^{n} b^{m} ∣ the m th Turing machine halts on input m}

$\{a^nb^m\mid \text{the }m\text{th Turing machine halts on input }m\}$ ?

{a^{n} b^{k n} ∣ k is one of David Richerby's favourite numbers}

$\{a^nb^{kn}\mid k\text{ is one of David Richerby's favourite numbers}\}$ ?

precisa saber é o seguinte

@Jiya Absolutamente, sim. Mas você precisa escolher o conjunto de expressões que deseja aceitar e escrever uma especificação formal dessas expressões. Então, sua máquina de Turing teria que analisar as expressões e decidir se elas correspondem a idiomas regulares ou não.

David Richerby

@Jiya Se os únicos idiomas que você considera são os do formulário

{a^{k x} b^{ℓ x} c^{m x} | x \geq 0}

$\{a^{kx}b^{\ell x}c^{mx}|x\ge 0\}$ Onde

k

$k$ ,

ℓ

$\ell$ e

m

$m$ são constantes, o idioma resultante é regular se, e somente se, dois ou três dos

k

$k$ ,

ℓ

$\ell$ e

m

$m$ são zero. Portanto, para idiomas definidos dessa maneira, o problema de determinar se o idioma resultante é regular é decidível. Mas, se você permitir relacionamentos mais complexos entre os números de

a

$a$ s

b

$b$ areia

c

$c$ s, pode ser indecidível se um idioma é regular. É por isso que é extremamente importante como os idiomas são especificados.

David Richerby

Respostas:

Myhill – Nerode realmente fornece uma caracterização das linguagens regulares, mas isso não é suficiente para mostrar que o problema é decidível. "Decidível" significa que existe um algoritmo (mais formalmente, uma máquina de Turing) que termina para cada entrada e, é claro, sempre dá a resposta correta. Portanto, nesse caso, você precisaria fornecer um algoritmo que, dado um idioma como entrada, determine se a relação Myhill – Nerode possui um número finito de classes de equivalência. Acontece que isso não pode ser feito para linguagens sem contexto; detalhes em seu livro didático de idiomas formais favorito.

Se você quiser decidir se uma linguagem geral é regular, uma outra sutileza é que você deve ter cuidado com o que é a entrada do seu algoritmo. A entrada deve ser uma sequência finita - caso contrário, apenas a leitura da entrada seria um algoritmo sem terminação. No caso de linguagens sem contexto, você pode usar uma gramática como uma representação finita de uma linguagem infinita. Para idiomas mais gerais, você precisaria ... bem, algo mais geral. Em última análise, porém, se você deseja lidar com todos os idiomas, está condenado. Sobre qualquer alfabeto finito, existem inúmeras línguas, mas apenas muitas seqüências finitas. Isso significa que você não pode descrever todos os idiomas usando cadeias finitas. ^{1 1}Portanto, tentar escrever um algoritmo para determinar se as linguagens arbitrárias fornecidas como entrada são regulares realmente falha antes de começar. Não é apenas que você não pode escrever o algoritmo: você não pode nem escrever a entrada!

Observe que isso não significa que você, um ser humano, não possa usar Myhill – Nerode para determinar se os idiomas são regulares. Significa apenas que você não pode escrever um conjunto de instruções precisas para me dizer como fazer isso. Em algum momento, qualquer conjunto de instruções teria que dizer algo como "E então brinque com ele para ver o que funciona" ou "A partir daí, você precisa descobrir por conta própria".

Em particular, isso significa que algumas linguagens devem ser indecidíveis, pois existem mais linguagens do que algoritmos.

David Richerby
fonte

Podemos contornar o problema com a codificação de entrada, restringindo-nos a todas as linguagens recursivamente enumeráveis, decidíveis ou mesmo sem contexto. Então, temos codificações de entrada "naturais" (gramáticas, máquinas de Turing, ...), mas ainda não podemos decidir a regularidade. Então, claramente, existem coisas mais sutis em andamento.

Raphael

Obrigado Raphael. Editei para deixar mais claro que a seção "destruição" se referia a não poder aceitar todos os idiomas como entradas.

David Richerby