Exercicio Teoria da Computação

[pic 1]

[pic 2]

[pic 3]

[pic 4]

[pic 5]

[pic 6]

10)

q1	X
q2	{q1, q5} {q3, q7}	X
q3	X	[pic 7]	X
q4	[pic 8]	X	[pic 9]	X
q5	X	{q0, q2}	X	[pic 10]	X
q6	[pic 11]	X	[pic 12]	X	{q0, q2} {q1, q5} {q3, q7}	X
q7	X	[pic 13]	X	{q4, q6}	X	[pic 14]	X
	q0	q1	q2	q3	q4	q5	q6

 

• {q0, q2} com a = {q1, q5}, não é marcado, então adiciona na lista;

{q0, q2} com b = {q6, q4}, não é marcado, então adiciona na lista;

• {q0, q4} com a = {q1, q7}, não é marcado, então adiciona na lista;

{q0, q4} com b = {q6, q7}, é marcado, marcar {q0, q4} e o que tem na lista;

• {q0, q6} com a = {q1, q7}, o de baixo marcou;

{q0, q6} com b = {q6, q3}, é marcado, marcar {q0, q6} e o que tem na lista;

• {q1, q3} com a = {q4, q0}, é marcado, marcar {q1, q3} e o que tem na lista; {q1,q3} com b = {q2, q4}, o de cima marcou;

• {q1, q5} com a = {q4, q6}, não é marcado, então adiciona na lista;

{q1, q5} com b = {q2, q0}, não é marcado, então adiciona na lista;

• {q1, q7} com a = {q4, q2}, não é marcado, então adiciona na lista;

{q1, q7} com b = {q2, q6}, não é marcado, então adiciona na lista;

• {q2, q4} com a = {q5, q7}, é marcado pelo debaixo;

{q2, q4} com b = {q4, q7}, é marcado, marcar {q2, q4} e o que tem na lista;

 

• {q2, q6} com a = {q5, q7}, é marcado pelo debaixo;

{q2, q6} com b = {q4, q3}, é marcado, marcar {q2, q6} e o que tem na lista;

 

• {q3, q5} com a = {q0, q6}, é marcado, marcar {q3, q5} e o que tem na lista;

{q3, q5} com b = {q4, q0}, é marcado pelo de cima;

• {q3, q7} com a = {q0, q2}, não é marcado, então adiciona na lista;

{q3, q7} com b = {q4, q6}, não é marcado, então adiciona na lista;

• {q4, q6} com a = {q7, q7}, igual, faz nada;

{q4, q6} com b = {q7, q3}, não é marcado, então adiciona na lista;

• {q5, q7} com a = {q6, q2}, é marcado, marcar {q5, q7} e o que tem na lista;

{q5, q7} com b = {q0, q6}, é marcado, marcar {q5, q7} e o que tem na lista.

 

Unificar os não marcados: q2 + q0 = q20. q1 + q5 = q15. q3 + q7 = q37.

...