Lista de Exercícios - Unidade 2

Prévia do material em texto

DISCIPLINA: LINGUAGENS FORMAIS E AUTÔMATOS 
LISTA DE EXERCÍCIO SEGUNDA UNIDADE 
Prof.: Marcelo Guerra 
 
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} 
 
b) {w | o número de 0s em w é o dobro do número de 1s} 
 
c) {w | w = wR, isto é, w é um palíndromo} 
 
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. 
 
 
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)