Soluções Newton MT e Decidibilidade

Prévia do material em texto

Soluções Newton Maquina de Turing e Decidibilidade
4. Construa uma MT que reconheça a linguagem denotada pela ER a(a + b) ∗ , assu-
mindo que o alfabeto é {a, b}, de forma que ela tenha:
(a) Um número mı́nimo de estados.
MT de 1 estado: ({0}, {a, b}, {h, t, a, b}, h, t, δ, 0, {0}), onde δ consta de: δ(0, b) =
[0, E], δ(0, t) = [0, E], δ(0, h) = [0, D].
(b) Um número mı́nimo de transições.
MT de 1 transição: ({0, 1}, {a, b}, {h, t, a, b}, h, t, δ, 0, {1}), onde δ consta de:
δ(0, a) = [1, E].
10. Seja a linguagem dos parênteses balanceados, que é gerada pela gramática ({P }, {(, )}, R, P ),
onde R consta das regras:
P → λ | (P ) | P P
Construa uma MT que reconheça tal linguagem.
3. Mostre que para toda gramática irrestrita existe uma equivalente na qual cada regra
tem o lado direito maior ou igual ao lado esquerdo ou é regra λ.
Basta substituir cada regra u → v em que |u| > |v|, u não é uma variável e v 6 = λ,
pela regra u → vX |u|−|v| , onde X é uma variável nova (basta uma variável nova X
para a gramática que está sendo criada), e acrescentar a regra X → λ.
4. Sejam L uma LRE e R uma linguagem recursiva. Mostre:
(a) L − R é uma LRE.
Como as linguagens recursivas são fechada sob complementação, R é recursiva.
Assim, R é LRE. Como as LRE’s são fechadas sob interseção, segue-se que
L ∩ R é LRE. Como L − R = L ∩ R, L − R é uma LRE.
(b) L − R pode não ser recursiva.
∅ é recursiva. E se L não é recursiva, L − ∅ = L não é recursiva.
(c) R − L pode não ser uma LRE.
Σ ∗ é recursiva. E Σ ∗ − L pode não ser uma LRE, pois as LRE’s não são
fechadas sob complementação.
9. Escreva MT’s não determinı́sticas que reconheçam as linguagens:
(b) {0 n | n não é primo}
Segue o diagrama de estados de uma MT de duas fitas não determinı́stica na Fi-
gura 6.12. No estado 3, a MT transita não deterministicamente para o estado 4,
tendo escrito na fita 2 uma palavra X n , onde 2 ≤ n < |w|, sendo w a palavra de
entrada. Nos estados 4 e 5 a MT verifica se |w| é múltiplo de n; se for, ela transita
para o estado final 6.
3. Mostre que se o problema da parada fosse decidı́vel, então toda LRE seria recursiva.
O problema de determinar se w ∈ L(M ) pode ser reduzido ao problema da parada,
pois para toda MT M existe uma MT M 0 que reconhece a mesma linguagem por
parada (Teorema 31).