Teoria da computação

EXERCÍCIOS
1) Considere um AFD M = ({q0, q1 q2, q3 q4, q5}, {a, b}, δ, q0, {q2, q3, q4}) onde: δ(q0, a) = q1 δ(q1, a) = q0 δ(q2, a) = q4 δ(q3, a) = q4 δ(q4, a) = q4 δ(q5, a) = q5 δ(q0, b) = q2 δ(q1, b) = q3 δ(q2, b) = q5 δ(q3, b) = q5 δ(q4, b) = q5 δ(q5, b) = q5
a) Construa e mostre o autômato M usando o software acima.

b) Mostre 2 cadeias reconhecidas por M.

c) Encontre o AFD M’ mínimo utilizando o algoritmo de minimização de AFDs.

d) Construa e mostre o autômato M’ usando o software acima.

2) Considere um AFD M = ({q0, q1 q2, q3 q4}, {a, b, c}, δ, q0, {q2, q4}) onde: δ(q0, a) = q0 δ(q3, a) = q4 δ(q4, a) = q4 δ(q0, b) = q1 δ(q1, b) = q1 δ(q2, b) = q3 δ(q4, b) = q1 δ(q0, c) = q3 δ(q1, c) = q2 δ(q2, c) = q2 δ(q3, c) = q3
a) Construa e mostre o autômato M usando o software acima.

b) Mostre 5 cadeias reconhecidas por M.

c) Encontre o AFD M’ mínimo utilizando o algoritmo de minimização de AFDs.

d) Construa e mostre o autômato M’ usando o software acima.

3) Considere um AFN M = ({q1, q2, q3 q4}, {a, b}, δ, q1, {q4}) onde: δ(q1, a) = {q1, q2} δ(q2, a) = {q3} δ(q1, b) = {q1} δ(q3, b) = {q4}
a) Construa e mostre o autômato M usando o software acima.

b) Mostre 5 cadeias reconhecidas por M.
c) Encontre o AFD equivalente de M e depois encontre o AFD M’ mínimo, utilizando o algoritmo de minimização de AFDs.
d) Construa e mostre os AFDs equivalente e mínimo (utilizando o algoritmo de minimização de AFDs) usando o software acima.

4) Considere o AFD abaixo e utilize o algoritmo de minimização de AFDs para encontrar o AFD mínimo equivalente.

5) Considere a Gramática Regular do tipo Gramática Linear à Direita, G = ({S, A, B, C}, {a,b}, P, S), onde P é dado por: S  A A  aB B  aC | bB | λ C  aC | bB | λ
a) Mostre 5 cadeias reconhecidas por M.
b) Utilize o software acima para construir e mostrar o Autômato Finito