3 Exercício de Linguagens Formais

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 
ALUNO: DIEGO XAVIER DE SOUSA - MATRÍCULA: 201808197372 
TURMA: 1001 SEMESTRE LETIVO: 2020.1 SALA: B204 TURNO: MANHÃ 
 
 
 
 EXERCÍCIO DE LINGUAGENS FORMAIS E AUTÔMATO 
 
 
EXERCÍCIOS DE FIXAÇÃO 
1. Minimize os autômatos mostrados nos diagramas a seguir: 
 
 
S1 + 
S2 + E 
S3 X X X 
S4 X X X E 
 S0 S1 S2 S3 
 
{SO,S2}➜S0,a S1 | S0,b S0 {SO,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 
 
S 3 
 
 
S 0 
 
 S 1 
 S 4 
 
 
 
S 2 
 
 
a) 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
S1 E 
S2 X X 
S3 X X + 
S4 X X E E 
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 
 
 
b) 
 
 
S 0 
 
 S 2 
 
 S 4 
 
 
 
 
 
S 1 
 
 S 3 
 S 5