Lista de Exercícios - Unidade 2 - Gabarito

Prévia do material em texto

Questão 1 – Minimize o seguinte autômato: 
 
Questão 2– Descreva gramáticas Livres de Contexto que geram as seguintes linguagens, todas 
sobre o alfabeto {0, 1}. 
a) {w | w contém pelo menos três 0s} 
G = ({S, A}, {0, 1}, R, S), onde: 
 S -> A0A0A0A 
A -> A0 | A1 |ε 
 
b) {w | o número de 0s em w é o dobro do número de 1s} 
G = ({S}, {0, 1}, R, S), onde: 
S -> 1S0S0 | 0S1S0 | 0S0S1 | ε 
 
c) {w | w = wR, isto é, w é um palíndromo} 
 G = ({S}, {0, 1}, R, S), onde: 
S -> 0S0 | 1S1 | 0 | 1 | ε 
Questão 3– Mostre que a gramática a seguir é ambígua: 
S → S + S 
S → S ∗ S 
S → (S) 
S → a 
 
 
 
Questão 4 – Considere a seguinte linguagem: 
 L = {wcwr | w ∈ ∑ = {a,b,c}* } 
a) Construa um ACP que reconheça a linguagem L. 
 
P = (Q, Σ, Γ, δ, q0, F) Q = {q0, q1} , ∑ = {a,b,c} , Γ = {a , b}, F = {q1} 
 
Funcao de Transicao (δ) 
1) δ (q0 , a , λ ) = { (q0, a ) } 
2) δ (q0 , b , λ ) = { (q0, b ) } 
3) δ (q0 , a , a ) = { (q0, aa ) } 
4) δ (q0 , a , b ) = { (q0, ab ) } 
5) δ (q0 , b , a ) = { (q0, ba ) } 
6) δ (q0 , b , b ) = { (q0, bb ) } 
7) δ (q0 , c , λ ) = { (q1, λ ) } 
8) δ (q0 , c , a ) = { (q1, a ) } 
9) δ (q0 , c , b ) = { (q1, b ) } 
10) δ (q1 , a , a ) = { (q1, λ ) } 
11) δ (q1 , b , b ) = { (q1, λ ) } 
 
 
 
b) Transforme o autômato construído no item a) para: 
 
 Um ACP com aceitação por pilha vazia (caso tenha construído com aceitação por estado 
final); 
 Um ACP com aceitação por estado final (caso tenha construído por pilha vazia)