A Teoria da Computação - Lista III

Resolução Atividade III

1. * Pode sim! Podemos inclusive através disto chamar um estado de aceitação ou rejeição.

* Não, pois o alfabeto da fita vai sempre conter o símbolo em branco, por outro lado o alfabeto de entrada não é obrigado a possuir o mesmo. Assim, se o símbolo branco estivesse no alfabeto de entrada a MT não saberia quando a entrada termina.

* Sabe-se que uma uma MT deve possuir pelo menos dois estados: O de Rejeição e o de Aceitação. Desta forma, não seria possível existir uma MT de um único estado.

2. Um problema de decisão é um problema onde para determinada entrada a resposta é sempre SIM ou NÃO. Alguns exemplos de problemas decisão incluem: Saber se um número x é ou não primo, se x é divisível por y, etc.

3. Note que G = {V, T, P, S} é irrestrita(qualquer gramática deste tipo não tem restrições sobre as produções de gramática). L é gerada por uma gramática irrestrita, logo L é recursivamente enumerável. Sabemos que se L é recursivamente enumerável, então existe uma MT que aceita esta linguagem. Portanto, este problema é decidível.

4. L = {< A, R > | A é AFD, R é uma ER e L(A) = L(R)}. Pode-se construir uma MT para executar isto através dos seguintes passos:

* Converter R em AFD C.

* Construir o AFD B(para representar a diferença simétrica).

* Verificar que o L(B) é vazia, e por fim: L(A) = L(C).

5. * Segue o Autômato Finito que mostra que o problema é decidível

* Segue o Autômato com Pilha que mostra que o problema decidível

* Segue a MT que mostra que o problema é decidível.

* Se a fita iniciar em branco não é possível retornar ao estado inicial, pois ela estaria no mesmo. Portanto, o problema é indecidível.

* O problema é decidível com a seguinte MT sendo sua Linguagem: L = {w | w pertence a {a, b} e N ° de b’s}: