Redutibilidade - Linguagens formais

UNIVERSIDADE FEDERAL DO VALE DO SÃO FRANCISCO – UNIVASF
Engenharia da Computação
Linguagens Formais e Autômatos

Redutibilidade

2013
1. Redutibilidade: Introdução
Dentre as diversas aplicações da teoria de linguagens formais, uma que se destaca entre as principais aplicações é a possibilidade de se determinar a decidibilidade (ou não) de problemas formulados como questões de decisão.
Um problema de decisão é um problema que admite, quando resolvido, apenas duas respostas: SIM ou NÃO. Um caso particular de um certo problema é chamado de instância daquele problema. Ao codificar todas as instâncias de um problema com resposta positiva, num alfabeto ∑ qualquer, eles formarão um conjunto de cadeias correspondente a uma linguagem L sobre ∑. Instâncias do problema com resposta negativa não pertencerão à L.
Assim, o problema deve ser inicialmente representado na forma de uma linguagem para que sua decidibilidade seja inferida a partir da classe de linguagens mais restrita a qual a linguagem pertence.
Se tal linguagem L for recursiva, existirá pelo menos uma Máquina de Turing que decidirá L. Ou seja, a partir da aceitação ou rejeição de uma cadeia pertencente à L pela Máquina de Turing, pode-se determinar se a resposta à instância correspondente do problema é afirmativa ou negativa, respectivamente.
Sabemos que uma Máquina de Turing recebe cadeias de uma linguagem e poderá apresentar três reações a elas: aceitará a linguagem, rejeitará, ou então executará tal linguagem infinitamente. Apenas as linguagens recursivamente enumeráveis serão suscetíveis à este último tipo de resposta. Por causa disso, as linguagens desta classe são chamadas de indecidíveis. Os problemas que quando representados numa linguagem resultam numa recursivamente enumerável também recebem a classificação de indecidíveis. Quando uma Máquina de Turing receber linguagens regulares, livres de contexto ou recursivas, é garantido que ela sempre parará em algum momento. Estas