Logica

Aula pr´tica 3 - 23 Outubro 2003 a Exerc´ ıcio de avalia¸˜o A: ca 1. Construa um aut´mato finito determinista cuja linguagem reconhecida seja o cono junto das sequˆncias de 0’s, 1’s e 2’s que n˜o come¸am por 1 e tais que o produto de e a c cada dois d´ ıgitos consecutivos seja 0 ou 2. 2. Verifique se a sequˆncia 001 ´ aceite pelo aut´mato. Justifique. e e o Resolu¸˜o: ca 1. Seja DA = (Q, I, δ, q0 , F ) onde • Q = {q0 , q1 , q2 , q3 }; • I = {0, 1, 2}; • δ : Q × I → Q ´ dada pela tabela; e • F = {q1 , q2 , q3 }; 2. δ ∗ (q0 , 001) = δ(δ ∗ (q0 , 00), 1) = δ(δ(δ ∗ (q0 , 0), 0), 1) = δ(δ(δ(δ ∗ (q0 , ), 0), 0), 1) = δ(δ(δ(q0 , 0), 0), 1) = δ(δ(q1 , 0), 1) = δ(q1 , 1) = q2 Dado que δ ∗ (q0 , 001) = q2 e q2 ∈ F , 001 ∈ LDA . δ q0 q1 q2 q3 0 q1 q1 q1 q1 1 − q2 − q2 2 q3 q3 q3 −

Exerc´ ıcio de avalia¸˜o B: ca 1. Construa um aut´mato finito determinista cuja linguagem reconhecida seja o cono junto das sequˆncias de 0’s, 1’s e 2’s que n˜o come¸am por 2 e tais que o produto de e a c cada dois d´ ıgitos consecutivos seja 0 ou 1. 2. Verifique se a sequˆncia 102 ´ aceite pelo aut´mato. Justifique. e e o Resolu¸˜o: ca

1

1. Seja DB = (Q, I, δ, q0 , F ) onde • Q = {q0 , q1 , q2 , q3 }; • I = {0, 1, 2}; • δ : Q × I → Q ´ dada pela tabela; e • F = {q1 , q2 , q3 }; 2. δ ∗ (q0 , 102) = δ(δ ∗ (q0 , 10), 2) = δ(δ(δ ∗ (q0 , 1), 0), 2) = δ(δ(δ(δ ∗ (q0 , ), 1), 0), 2) = δ(δ(δ(q0 , 1), 0), 2) = δ(δ(q2 , 0), 2) = δ(q1 , 2) = q3 Dado que δ ∗ (q0 , 102) = q3 e q3 ∈ F , 102 ∈ LDB . δ q0 q1 q2 q3 0 q1 q1 q1 q1 1 q2 q2 q2 − 2 − q3 − −

2