Decidibilidade Teoria da computação
Por: Driélle Betina • 25/11/2015 • Seminário • 1.936 Palavras (8 Páginas) • 505 Visualizações
Decidibilidade
Linguagens Decidíveis
Uma linguagem decidível é uma linguagem em que existe uma máquina de Turing que, quando recebe uma cadeia de entrada aceita-a ou à rejeita, dessa forma, a máquina de Turing sempre a decide.
[pic 2]
Exemplo 1:
Neste exemplo será testado o problema de aceitação referente a um AFD, ou seja, se o mesmo aceita uma cadeia w. Para isso será estabelecida uma linguagem Aafd e sua decibilidade é constatada após o processo, ela esta definida como:
Aafd = {
Algoritmo para a máquina de Turing M:
- Simule o autômato B com respeito à entrada w
- Verifique se ela termina em um estado de aceitação, caso sim , aceita, senão, rejeite.
Detalhes referentes á simulação do AFD foram abstraídos para não fujir ao escopo, mas é bom deixar claro que a maquina M faz verificações de corretude da entrada
Na realidade tanto AFDs tal como o acima,um AFN ou expressão regular poderiam ser computados por uma máquina de Turing pois todos eles podem ser convertidos uns para os outros.
O próximo exemplo faz referencia ao chamado teste de vacuidade(Sipser) para a linguagem de um autômato finito.Nela o objetivo é verificar a aceitação ou não de alguma cadeia por um AFD.
Exemplo 2:
Vafd = { | A é um AFD e L(A) = ø }
Vafd é decidível ?
Algoritmo:
- Marque o estado inicial A e vá para 2.
- Enquanto nenhum novo estado for marcado, marque qualquer estado que possua uma transições chegando nele vindos de estados já macardos.
- Se nenhum estado de aceitação estiver marcado, aceite, senão, rejeite.
Os exemplos à seguir tratam de problemas decidíveis com relação à linguagens livres do contexto.
Exemplo 3:
Analogamente ao problema de teste de aceitação do exemplo 1, o exemplo atual demonstra o problema de testar a geração de uma cadeira por um GLC para assim constatar a decibilidade de uma linguagem, no caso, Aglc definida como:
Aglc = {
A primeira idéia que surge é tentar todas as possíveis derivações de G para constatar se alguma delas é igual à w. Apesar de simples e correta, a idéia é inviável tendo em vista que se G não gerar w a máquina entraria em loop infinito.
Assim uma forma mais inteligente faz-se necessária. Utilizando a Forma Normal de Chomsky, é certo que qualquer derivação terá 2n-1 com n sendo igual ao comprimento de w. Com base nisso e abstraindo dados específicos sobre a construção da Forma Normal o algoritmo ficará como:
Algoritmo sobre
- Aplique o processo para converter G de sua forma inicial para um GLC equivalente na Forma Normal de Chomsky.
- Verifique o comprimento de w, se for maior que 0, liste todas as derivações de 2n-1 passos ( com n = |w| ) , senão liste todas as derivações com 1 passo.
- Se alguma das derivações gerar w, aceite, caso contrário, rejeite.
[pic 3]
Decidibilidade: Problemas Decidíveis Concernentes a Linguagens Regulares:
Começamos com certos problemas computacionais concernentes a autômatos finitos. Damos algoritmos para testar se um autômato finito aceita uma cadeia, se a linguagem de um autômato finito é vazia, e se dois autômatos finitos são equivalentes. Note que escolhemos representar vários problemas computacionais por meio de linguagens. Fazer isso é conveniente porque temos já estabelecida uma terminologia para lidar com linguagens. Por exemplo, o problema da aceitação para AFDs de testar se um autômato finito determinístico específico aceito uma dada cadeia pode ser expresso como uma linguagem, AFD. Essas linguagens contem às codificações de todos os AFDs juntamente com cadeias que os AFDs aceitam.
Seja AFD = {[B, w] | B é um AFD que aceita a cadeia de entrada w}.
O problema de se testar se um AFD B aceita uma entrada w é o mesmo que o problema de se testar se [B, w] é um membro da linguagem AFD. Similarmente, podemos formular outros problemas computacionais em termos de testar pertinência em uma linguagem. Mostrar que a linguagem é decidível é o mesmo que mostrar que o problema computacional é decidível. No teorema a seguir mostramos que AFD é decidível. Portanto, esse teorema mostra que o problema de se testar se um dado autômato finito aceita uma dada cadeia é decidível.
IDÉIA DA PROVA: Simplesmente precisamos apresentar uma MT M que decide AFD.
M = “Sobre a entrada [B, w], onde B é um AFD e w é uma cadeia:
1. Simule B sobre a entrada w.
2. Se a simulação termina em um estado de aceitação, aceite. Se ela termina em um estado de não-aceitação, rejeite.”
PROVA: Mencionamos apenas alguns poucos detalhes de implementação dessa prova. Para aqueles de vocês familiarizados com escrever programas em alguma linguagem de programação padrão, imagine como você escreveria um programa para realizar a simulação. Primeiro, vamos examinar a entrada [B, w]. Ela é uma representação de um AFD B juntamente com uma cadeia w. Uma representação razoável de B é simplesmente uma lista de seus cinco componentes, Q, Σ, δ, q0 e F. Quando M recebe sua entrada, M primeiro determina se ela representa apropriadamente um AFD B e uma cadeia w. Se não, M rejeita. Então M realiza a simulação diretamente. Ela mantém registro do estado atual de B e da posição atual de B na entrada w escrevendo essa informação na sua fita. Inicialmente, o estado atual de B é q0 e a posição atual de B sobre a entrada é o símbolo mais à esquerda de w. Os estados e a posição são atualizados conforme a função de transição especificada δ. Quando M termina de processar o ultimo símbolo de w, M aceita a entrada se B está em um estado de aceitação; M rejeita a entrada se B está em um estado de não-aceitação.
...