P1 LFA - Bruno_Ogata

Prévia do material em texto

Nome: Bruno Hideki Amadeu Ogata Matrícula: 140884 
 
Questão 1) (2.5 Pontos) Sejam as linguagens LA e LB descritas, 
respectivamente, pelos autômatos A e B: 
DFA A = {{q0, q1, q2}, {0,1}, δ = {(q0,0)=q2, (q0,1)=q1, (q1,0)=q0, (q1,1)=q0, 
(q2,0)=q2, (q2,1)=q2}, q0, {q0,q1}} DFA B = {{q0, q1}, {0,1}, δ = {(q0,0)=q1, 
(q0,1)=q0, (q1,0)=q0, (q1,1)=q1}, q0, {q1}} 
 
(a) Calcule o Delta Estendido (δ chapéu) da string 101110 a partir do estado 
q0 do DFA A. 
 
R: Vamos calcular o Delta Estendido da string w = 101110 para o DFA A: 
𝛿 ̂(q0, w), com w = {101110} 
𝛿 ̂(q0, ε) = q0 
𝛿 ̂(q0, 1) = δ(𝛿 ̂(q0, ε), 1) = δ(q0, 1) = q1 
𝛿 ̂(q0, 10) = δ(𝛿 ̂(q0, 1), 0) = δ(q1, 0) = q0 
𝛿 ̂(q0, 101) = δ(�̂�(q0,10), 1) = δ(q0, 1) = q1 
𝛿 ̂(q0, 1011) = δ(𝛿 ̂(q0, 101), 1) = δ(q1, 1) = q0 
𝛿 ̂(q0, 10111) = δ(�̂�(q0, 1011), 1) = δ(q0, 1) = q1 
𝛿 ̂(q0, 101110) = δ(�̂�(q0, 10111), 0) = δ(q1, 0) = q0 
 
(b) A string apresentada em (a) pertence a linguagem definida pelo DFA A? 
Justifique. 
 
R: A string 101110 pertence a linguagem definida pelo DFA A, visto que ao 
aplicar o Delta Estendido a string terminou no estado q0, que é um estado final 
do DFA. 
 
(c) Construa um DFA que reconheça LA∩LB utilizando o produto dos 
autômatos. Represente pelo diagrama de transições. 
 
R: Realizando o produto entre os DFA’s, apenas observando as transições 
entre os estados dos DFA’s eu obtive, inicialmente, o seguinte autômato: 
 
Com q3 representando o estado q0 do DFA B e q4 o estado q2 do DFA B, 
mas note que esse autômato pode ser representado de uma forma mais 
simples, como a seguinte: 
 
 
 
 
 
 
Questão 2) (2.5 Pontos) Considere o ε-NFA C abaixo: 
 
 
 
(a) Calcule o fechamento de cada estado do ε-NFA C. 
 
R: Pela observação do ε-NFA nota-se que o fechamento de q0 = {q0, q2}, o 
fechamento de q1 = {q1}, o fechamento de q2 = {q2}, o fechamento de q3 = 
{q3} e o fechamento de q4 = {q4}. 
 
(b) Converta o ε-NFA C para um DFA equivalente. Represente o DFA por uma 
tabela de transição. 
 
R: A conversão desse ε-NFA para DFA é dada pela seguinte tabela de 
transição: 
 
 0 1 
→q0 ⊘ {q1} 
q1 ⊘ {q0, q2} 
*q0q2 {q3} {q1, q4} 
q3 {q2} ⊘ 
q1q4 {q2} {q0, q2} 
*q2 {q3} {q4} 
q4 {q2} ⊘ 
 
 
 
 
 
 
 
 
 
 
 
Questão 3) (3.0 Pontos) Considerando o DFA D = ({q0,q1,q2,q3,q4,q5,q6,q7}, 
{a,b}, q0, δ, {q2}) 
_δ a b_ 
q0 q1 q5 
q1 q6 q2 
q2 q0 q2 
q3 q3 q7 
q4 q7 q5 
q5 q2 q6 
q6 q6 q4 
q7 q6 q2 
 
 
a) Encontre a tabela de estados distinguíveis. 
 
R: Temos a seguir a tabela de estados distinguíveis: 
 
Q1 X1 
Q2 X0 X0 
Q3 X2 X1 X0 
Q4 X1 X0 X2 
Q5 X1 X1 X0 X1 X1 
Q6 X2 X1 X0 X2 X1 X1 
Q7 X1 X0 X1 X1 X1 X1 
 Q0 Q1 Q2 Q3 Q4 Q5 Q6 
 
 
b) Quais são os conjuntos de estados equivalentes? 
 
R: Olhando a tabela acima percebe-se que os conjuntos de estados 
equivalentes são {Q0, Q4} e {Q1, Q7}, sendo estes os estados que serão 
agrupados no processo de minimização a seguir. 
 
 
c) Desenhe o diagrama de transição do DFA mínimo equivalente ao DFA D. 
 
R: O diagrama de transição do DFA mínimo é dado por: 
 
 
 
 
 
 
 
 
Questão 4) (2.0 Pontos) Prove que a linguagem abaixo é Regular construindo 
uma expressão regular que a represente: 
L = {w | w ∈ (0,1)* e contêm as substrings 00 e 11} 
 
R: Podemos representar essa linguagem através da seguinte expressão 
regular: 
 
RE = ((1+0)*(00)(1+0)*(11)(1+0)*) + ((1+0)*(11)(1+0)*(00)(1+0)*)