APS Linguagens Formais e Autômatos

Prévia do material em texto

Linguagens Formais e Autômatos
 Atividade Prática Supervisionada
Prof. Charles Ferreira
CURSO: ENGENHARIA DA COMPUTAÇÃO	 		SEMESTRE: 9º
1. Dado o alfabeto Σ {a, b}, construa autômatos finitos para as seguintes linguagens:
 (a) {b (ab)n b | n ≥ 0 } 
(b) {amb n | m+n é par}
2. Seja Σ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, construa um autômato finito para seguinte linguagem: (a) { x ∈ Σ + | a sequência descrita por x corresponda a um valor inteiro divisível por 5}
3 - Qual a linguagem definida pelo seguinte autômato? 
L = {w ∈ {a, b}* | |w|a = 2n+1 ∧ |w|b = 2m+1 ∧ n, m≥0 }
4. Escreva uma Expressão Regular que reconheça as seguintes linguagens: 
(a) O conjunto de cadeias sobre {0, 1} que tenha ao menos um 1. 
(0+1)*1(0+1)*
(b) O conjunto de cadeias sobre {0, 1} que tenha no máximo um 1.
 0*(1+ʎ)0*
5. Construa as gramáticas livres de contexto que gerem as seguintes linguagens:
(a) L = { wcwR | w ∈ {a, b}*}
	R
	
	S
	S
	
	aSa
	S
	
	bSb
	S
	
	a
	S
	
	b
	S
	
	λ
(b) L = { w ∈ {0, 1}* | w começa e termina com o mesmo símbolo} 
	R
	
	aPa
	R
	
	bPb
	P
	
	aP
	P
	
	bP
	P
	
	λ
(c) L = { w ∈ {0,1}* | o comprimento de w é ímpar}
	R
	
	T
	T
	
	TTT
	T
	
	1
	T
	
	0