a b

(q0,0) (q0,110) (q2, )

(q0,1) (q0,111) (q1, )

(q1,1) (q1, )

(q1,0) (q2, )

3(a), pag. 112: anb2n

3(b) pag. 112: wcwR

a b c

(q0,0) (q0,10) (q0,20) (q1,0)(q0,1) (q0,11) (q0,21) (q1,1)(q0,2) (q0,12) (q0,22) (q1,2)(q1,0) (q2,)(q1,1) (q1, )(q1,2) (q1, )

Só dicas ...

• 3(c): anbmcn+m

– basta empilhar a’s e b’s e desempilhá-los com os c’s

• 3(d): anbn+mcm

– basta empilhar a’s, desempilhá-los com alguns dos b’s até que todos os a’s sejam desempilhados passando a empilhar os b’s restantes que serão desempilhados com os c’s

3(e): anbm, n≤m≤3n

S aSb | aSbb | aSbbb | 1 2 3 4S aSA1 | aSA2 | aSA3 |

A1 b

A2 bA1

A3 bB

B bA1

Será mesmo que L(G)=L?

• Provemos então que

L(G)={anbm, n≤m≤3n}• L(G)L i.e. Se Sn+1anbm, então n≤m≤3n.

Por indução em n.(base) n=0 S n=1 S2ab, S2abb, S2abbb(passo) (Se Sn+1anbm, então n≤m≤3n) implica (Sn+2an+1bm’ com n+1≤m’≤3(n+1))

• Sn+1anbm implica que Sn anSbm anbm

a) Sn anSbm anaSbbm

n≤m, logo n+1≤m+1m≤3n, logo m+1≤3n+3

b) Sn anSbm anaSbbbm

n≤m, logo n+1≤m+2m≤3n, logo m+2≤3n+3

c) Sn anSbm anaSbbbbm

n≤m, logo n+1≤m+3m≤3n, logo m+3≤3n+3

• L(G)L Dado anbm com n≤m≤3n, seja k=m-n i.e. m=n+k.

• k=0, k=n, k=2n é trivial!• 0<k<n:

S n-k an-kSbn-k k anSbn+k anbn+k 1 2 4

• n<k<2nk=2p, 1≤p

S n-p an-pSbn-p p anSbn+2p anbn+k 1 3 4

k=2p-1, 1≤p Sn-p an-pSbn-pan-p+1Sbn-p+2p-1anbn+2p-1

1 2 3

S aSA1 | aSA2 | aSA3 |

A1 b

A2 bA1

A3 bB

B bA1

δ(q,a,S)={(q,SA1), (q,SA2), (q,SA3), (q,)}

δ(q,b,A1)={(q,)}

δ(q,b,A2)={(q,SA1)}

δ(q,b,A3)={(q,B)}

δ(q,b,B)={(q,A1)}

Para exercitar ...

3(f):S aaX | aXa | baY | bYa | X bS | aXX | bY aS | bYY | a

3(g):S aaSbS | aSbSaS | bSaaS |

Cuidado com o (h)

• Posto que L não é uma LLC uma vez que jogando contra o diabo para cada k que ele escolha basta dar akbkck e ele perde.

3(i): L={w : |w|a+|w|b=|w|c}

a b c

(q0,z) (q0,0z) (q0,0z) (q0,1z) (qf,z)

(q0,0) (q0,00) (q0,00) (q0, )

(q0,1) (q0, ) (q0, ) (q0,11)

Descrições Informais de MTs

• Uma máquina de Turing para {ww | w{a,e}*}

• Dada x como entrada, varrer até encontrar o primeiro símbolo vazio, contando o número de símbolos mod 2 rejeitando caso x não seja par.

• Escreve um marca de fim ┤ à direita e repetidamente varre um lado e outro da fita.

• Em cada passada da direita para a esquerda, marca o primeiro a ou e não marcado com '.

• Na passada da esquerda para a direita marca com `.

• Vai assim até todos os símbolos estarem marcados.

• por exemplo ...

├aaeeaaaeea■■■■...├aaeeaaaeeá┤■■■■...├àaeeaaaeeá┤■■■■...├àaeeaaaeéá┤■■■■...├ààeeaaaeéá┤■■■■......├ààèèàááééá┤■■■■...• agora varre a fita da esquerda para a

direita repetidamente. Em cada passo apaga o primeiro marcado com ` mas se lembra deste símbolo

• daí varre até o primeiro não marcado, checa se igual ao apagado e apaga-o;

• se os símbolos não são iguais rejeita;

• se todos os símbolos forem apagados, aceita.

├ààèèàááééá┤■■■■...├■àèèà■áééá┤■■■■...├■■èèà■■ééá┤■■■■......├■■■■■■■■■■┤■■■■...

Número de a's é primo

• Crivo de Eratóstenes:2 3 4 5 6 7 8 9 10 11 12 13 3 5 7 9 11 13 5 7 11 13

• seja ap na fita├aaaaaaaaaaaaaOOO...(por razões tipográficas O vai representar o

células vazia)

• se p=0 rejeita, se p=1 aceita;• se tem pelo menos dois a's, apaga o

primeiro, varre até o último a e o substitui por $

• agora temos um a nas posições 2,3, ..., p-1 e $ na posição p.

├Oaaaaaaaaaaa$OOO...• repita o laço: • varrendo do começo ├, encontre o

primeiro símbolo não-vazio, digamos na posição m

• Então m é primo! (invariante);• se o símbolo for $, p é primo e pare• senão, marque o a com ^ e tudo entre

ele e ├ com ':├Óâaaaaaaaaaa$OOO...• entra num laço para apagar todos os

símbolos que ocorrem em posições que são múltiplas de m.

• primeiro apaga o a debaixo de ^. ├ÓÔaaaaaaaaaa$OOO...

• Desloca as marcas uma por vez para direita a uma distância igual ao número de marcas:

├OOáâaaaaaaaa$OOO...• apaga o símbolo sob ^, que está na

posição 2m.├OOáÔaaaaaaaa$OOO...• mantenha-se deslocando as as

marcas e apagando os símbolos sob ^ até o fim.

├OOaOaOaOaO$'ÔOO...

• se estivermos para apagar o $, rejeite a cadeia!

• senão, volta e repete todo o pro-cesso acima; encontre o primeiro símbolo não vazio mais a esquerda marque-o com ^ e marca tudo a sua esquerda com ';

├ÓÓâOaOaOaO$OOO...• e vai deslocando e apagando:├OOOOaOaOOÓ$'ÔOO...

• volta e repete até ou tenta-se apagar $ e rejeita-se a cadeia ou se apagam todos os a's e aceita.

├OOOOaOaOOÓ$'ÔOO...├ÓÓÓÓâOOÓ$'ÔOO...├OOOOOÓÓÓ$'ÔOO...