Upload
thiago-ferreira-bueno
View
214
Download
0
Embed Size (px)
Citation preview
7/24/2019 exercicios Mquinas universais
1/5
Teoria da Computao
Cincia da ComputaoProf. Esp. Giulliano
Mquina de Turing
1. Atravs da tabela de estados abaixo, determinar se as palavrasso aceitas ou reeitadas.
a. M = ({0, 1}, {q0, q1, q2}, , q0, {q2}, , , !"
0 1 !q0 !"#, #, $% !"#, 1, $% !"#, &, E% !"#, ', $%q1 !"(, #, $% ) ) )q2 ) ) ) )
*eitura+ sobre o alfabeto #, 1-, "ue veri"ue se os n/merosbin0rios fornecidos pelo usu0rio so n/meros bin0rios pares
#. M = ({1}, {q0, q1, q2, q$, q%}, , q0, {q%}, , , !"
1 !
q0 ) ) !"1, ', $%q1 !"(, 1, $% ) )q2 !", 1, $% ) )q$ !"(, 1, $% !"2, &, E% )q% ) ) )
*eitura+ 3obre o alfabeto 1-. 3upon4a"ue as palavras de entrada so n/merosnaturais representados em un0rio, onde,
por exemplo, denotado por 111, 2 denotado por 1111, e assim por diante. A
&ntrada 'tatu1#1#1#11111#
&ntrada 'tatu11111111111111
7/24/2019 exercicios Mquinas universais
2/5
m0"uina deve aceitar os naturais pares e reeitar os naturais
5mpares.). M = ({0, 1}, {q0, q1, q2}, , q0, {q2}, , , !"
0 1 !q0 !"#, #, $% !"#, 1, $% !"1, &, E% !"#, ', $%q1 ) !"(, 1, $% ) )q2 ) ) ) )
*eitura+ sobre o alfabeto #, 1-, "ue veri"ue se os n/merosbin0rios fornecidos pelo usu0rio so n/meros bin0rios 5mpares.
(. Para cada m0"uina de 6urin7 abaixo, determinar se as palavrasso aceitas ou reeitadas.
a. M = ({a, #}, {q0, q1, q2, q$, q%}, , q0, {q%}, {*, +}, , !"#.
*eitura+ 3obre o alfabeto a, b-, "ueveri"ue o duplo balanceamento daentrada fornecida pelo usu0rio, ousea, $ 8 anbn9 n : #-
&ntrada 'tatu1#111#1#1#11
7/24/2019 exercicios Mquinas universais
3/5
). M = ({a, #, }, {q0, q1, q2, q$, q%, q-, q, q/, q, q}, , q0,{q}, {*, +}, , !"
*eitura+ ;eri"ue se duas palavras sobre o alfabeto a, b, ado como separador das duas palavras.d. M = ({1, }, {q0, q1, q2, q$, q%, q-, q}, , q0, {q}, , , !"
&ntrada 'tatuaabbbbaaababab
&ntrada 'tatuabb
7/24/2019 exercicios Mquinas universais
4/5
*eitura+ 3obre o alfabeto 1, )-, "ue reali>e a subtrao un0ria de doisn/meros fornecidos pelo usu0rio
e. M = ({a, #}, {q0, q1, q2, q$, q%}, , q0, {q%}, {*, +}, , !"
&ntrada 'a3da4ita 'tatu111)11 1111)111 111)1111 indiferente)
?ndiferente
&ntrada 'tatubababbaabaabaabbaa
7/24/2019 exercicios Mquinas universais
5/5
*eitura+ 3obre o alfabeto a, b-, "ue recon4ea palavras "ueconten4am a mesma "uantidade de s5mbolos a@s e b@s,independentemente da ordem como os s5mbolos apaream naentrada.