liguagens formais e automatos 13 04 2020

Prévia do material em texto

FACULDADE ESTÁCIO DE TERESINA 
 
 
CURSO: BACHARELADO EM CIÊNCIAS DA COMPUTAÇÃO 
DISCIPLINA: LINGUAGENS FORMAIS E AUTÔMATOS 
DOCENTE: JOSÉ CARLOS CORREIA 
TURMA:1001 SEMESTRE LETIVO:2020.1 SALA: B204 TURNO: MANHÃ 
ALUNO: JOÃO VICTOR BARBOSA DE MELO 
MATRÍCULA: 20190132263 
 
ATIVIDADE DE LINGUAGENS FORMAIS E AUTÔMATOS 
Exercícios de fixação 
1.Minimize os autômatos mostrados nos diagramas a seguir: 
a) 
S1 + 
S2 + ᵋ 
S3 x x x 
S4 x x x ᵋ 
 S0 S1 S2 S3 
 
{SO,S2}: S0,a S1/ S0,b S0 {S0,S1}: S0,a S1 / S0,b S0 
 S2,a S4/S2,b S2 S1,a S3 / S1,b S2 
{S1,S2}: S1,a S3 / S1,b S2 {S3,S4}: S3,a S3 / S3,b S2 
 S2,a S4 / S2,b S2 S4,a S3 / S4,b S2 
 
b) 
S1 ᵋ 
S2 X X 
S3 X X + 
S4 X X ᵋ ᵋ 
S5 + + X X X 
 S0 S1 S2 S3 S4 
 
{S0,S1}: S0,a S1 / S0,b S2 {S0,S5}: S0,a S1 / S0,b S2 
 S1,a S0 / S1,B S3 S5,a s5 / S5,b S5 
{S1,S5}: S1,a S0 / S1,b S3 {S2,S3}: S2,a S4 / S2,b S5 
 S5,a S5 / S5,b S5 S3,a S4 / S3,b S5 
{S2,S4}: S2,a S4 / S2,b S5 {S3,S4}: S3,a S4 / S3,b S5 
 S4,a S4 | S4,b S5 S4,a S4 | S4,b S5