Prova de Teoria dos Automatos E LINGUAGENS FORMAIS E COMPUTABILIDADE

Prévia do material em texto

2º NPC DE LINGUAGENS FORMAIS E COMPUTABILIDADE
Prof. Edson Pessoa
Data 20 de Novembro de 2017
ALUNO:___________________________________________________Matricula____________
Questão1:Considere os autômatos M1, M2e M3a seguir:
	M1
	Estados/Σ
	a
	b
	>>>>
	q0
	q1
	q0
	<<<<
	q1
	q2
	q1
	M2
	Estados/Σ
	a
	b
	>>>>
	q0
	q1
	q0
	
	q1
	q2
	q1
	<<<<
	q2
	---
	q2
	M3
	Estados/Σ
	a
	b
	λ
	>>>>
	q0
	q2
	---
	q1
	<<<<
	q1
	---
	q1
	q3
	
	q2
	---
	q3, q0
	--- 
	
	q3
	q4
	---
	---
	
	q4
	---
	q1
	---
Pede-se:
a)A Expressão Regular da Linguagem aceita porM1,M2eM3.
b) Transformar o LambdaNAF M3em umDAF M4.
c) Usar o Método da Eliminação de Estados para obter a Expressão Regular deM4.
d) Determinar aGramática Regularque gera a Linguagem aceita porM4.
e)Projetar os Autômatos correspondentes as linguagens:
i) L1(M1)UL(M2). (União de L1e L2)
ii) L2(M1)L(M2). (Concatenação de L1e L2)
iii)L3(M1)*. (Estrela de L3)
Questão 2:Dado a Gramatica Regular a seguir, pede-se:
GR: S → aA
A → aB
B → aB | bB | bC
C→ bD
D→ ʎ
a) ALinguagemgerada porGR.
b) UmDAFque aceite oComplementode L(G).