AV1 - Linguagens Formais

Prévia do material em texto

Q1
	PARTE 1										PARTE 2
	Convertendo o AFNε para AFN										Convertendo o AFN para AFD
	δ	0	1	2	ε		Para o AFNε temos F' = {q0 ,q1, q3} pois:				δ''	0	1	2
	q0	{q0}	Ø	Ø	{q1}		Fε(q0) = {q0, q1, q3}				q0	{q0, q1, q2}	{q1, q2}	{q2}
	q1	Ø	{q1}	Ø	{q2}		Fε(q1) = {q1, q2}				q1	Ø	{q1, q2}	{q2}
	q2	Ø	Ø	{q2}	Ø		Fε(q2) = {q2}				q2	Ø	Ø	{q2}
	Contrução da função de transições δ										Construindo tabela de transições do AFD (δ'')					Marcando estados finais
	δ({q0}, ε) = {q0, q1, q2}										δ''		0	1	2	δ''		0	1	2
	δ({q0}, ε) = {q1, q2}										s0=	{q0}				s0=	{q0}
	δ({q0}, ε) = {q2}										s1=	{q1}				s1=	{q1}
											s2=	{q2}				s2=	{q2}
	Cálculo										s3=	{q0, q1}				s3=	{q0, q1}
	■ δ'(q0, 0) = δ({q0}, 0)					■ δ'(q1, 0) = δ({q1}, 0)					s4=	{q0, q2}				s4=	{q0, q2}
	=	Fε({r | r ∈ δ (S,0) ∧ S ∈ δ({q0}, ε})				=	Fε({r | r ∈ δ (S,0) ∧ S ∈ δ({q1}, ε})				s5=	{q1, q2}				s5=	{q1, q2}
	=	Fε({r | r ∈ δ (S,0) ∧ S ∈ {q0, q1, q2}})				=	Fε({r | r ∈ δ (S,0) ∧ S ∈ {q1, q2}})				s6=	{q0, q1, q2}				s6=	{q0, q1, q2}
	=	Fε({q0})				=	Fε({ }) = INDEFINIDO				s7=	Ø				s7=	Ø
	=	{q0, q1, q2}				=	Fε = Ø
											Verificar ocorrencias e alinhar correspondencias					Eliminar Estados Inalcansáveis
	■ δ'(q0, 1) = δ({q0}, 1)					■ δ'(q1, 1) = δ({q1}, 1)					δ''		0	1	2	δ''		0	1	2
	=	Fε({r | r ∈ δ (S,1) ∧ S ∈ δ({q0}, ε})				=	Fε({r | r ∈ δ (S,1) ∧ S ∈ δ({q1}, ε})				s0=	{q0}	s6	s5	s2	s0=	{q0}	s6	s5	s2
	=	Fε({r | r ∈ δ (S,1) ∧ S ∈ {q0, q1, q2}})				=	Fε({r | r ∈ δ (S,1) ∧ S ∈ {q1, q2}})				s1=	{q1}	s7	s5	s2	s1=	{q1}	s7	s5	s2
	=	Fε({q1})				=	Fε({q1})				s2=	{q2}	s7	s7	s2	s2=	{q2}	s7	s7	s2
	=	{q1, q2}				=	{q1, q2}				s3=	{q0, q1}	s6	s5	s2	s3=	{q0, q1}	s6	s5	s2
											s4=	{q0, q2}	s6	s5	s2	s4=	{q0, q2}	s6	s5	s2
	■ δ'(q0, 1) = δ({q0}, 2)					■ δ'(q1, 2) = δ({q1}, 2)					s5=	{q1, q2}	s7	s5	s2	s5=	{q1, q2}	s7	s5	s2
	=	Fε({r | r ∈ δ (S,2) ∧ S ∈ δ({q0}, ε})				=	Fε({r | r ∈ δ (S,2) ∧ S ∈ δ({q1}, ε})				s6=	{q0, q1, q2}	s6	s5	s2	s6=	{q0, q1, q2}	s6	s5	s2
	=	Fε({r | r ∈ δ (S,2) ∧ S ∈ {q0, q1, q2}})				=	Fε({r | r ∈ δ (S,2) ∧ S ∈ {q1, q2}})				s7=	Ø	s7	s7	s7	s7=	Ø	s7	s7	s7
	=	Fε({q2})				=	Fε({q2})
	=	{q2}				=	{q2}				Montar o AFD a partir de (δ)					Eliminar estados que não possuem saída para estados finais
	■ δ'(q2, 0) = δ({q2}, 0)					LOGO, O AFN EQUIVALENTE É:
	=	Fε({r | r ∈ δ (S,0) ∧ S ∈ δ({q2}, ε})
	=	Fε({r | r ∈ δ (S,0) ∧ S ∈ {q2}})				δ'	0	1	2
	=	Fε({ }) = INDEFINIDO				q0	{q0, q1, q2}	{q1, q2}	{q2}
	=	Fε = Ø				q1	Ø	{q1, q2}	{q2}
						q2	Ø	Ø	{q2}
	■ δ'(q2, 1) = δ({q2}, 1)
	=	Fε({r | r ∈ δ (S,1) ∧ S ∈ δ({q2}, ε})
	=	Fε({r | r ∈ δ (S,1) ∧ S ∈ {q2}})
	=	Fε({ }) = INDEFINIDO
	=	Fε = Ø
	■ δ'(q2, 2) = δ({q2}, 2)
	=	Fε({r | r ∈ δ (S,2) ∧ S ∈ δ({q2}, ε})
	=	Fε({r | r ∈ δ (S,2) ∧ S ∈ {q2}})
	=	Fε({q2})									Teste com a palavra 10020120
	=	{q2}									Ciclo	t0	t1	t2	t4	t5	t6	t7	t8
											Entrada	1	0	0	2	0	1	2	0
											Estado	s5	s5	s5	s2	s2	s2	s2	s2
											Resultado	OK!
Q2
	Parte 1										Parte 2
	CONVERTER AFN PARA AFD										TRANSFORMAR O AFD EM GRAMATICA
	δ	a	b	c							s0 = S		S -> bA | aB
	q0	{q0, q1}	{q1}	Ø							s1 = A		A -> bC | cD
	q1	Ø	{q1, q2}	{q3}							s4 = B		B -> bC | cD | ε
	q2	Ø	Ø	{q2, q3}							s7 = C		C -> cE
	q3	Ø	Ø	Ø							s3 = D		D -> ε
											s9 = E		E -> ε
	CONSTRUIR TABELA DE TRANSIÇÕES PARA O AFD (δ) 
	δ		a	b	c	δ		a	b	c
	s0= {q0}					s8= {q1, q3}
	s1={q1}					s9= {q2, q3}
	s2= {q2}					s10= {q0, q1, q2}
	s3= {q3}					s11= {q0, q2, q3}
	s4= {q0, q1}					s12= {q0, q1, q3}
	s5= {q0, q2}					s13= {q1, q2, q3}
	s6= {q0, q3}					s14= {q0, q1, q2, q3}
	s7= {q1, q2}					s15= Ø
	MOSTRAR CONJUNTO COM ESTADOS FINAIS
	δ		a	b	c	δ		a	b	c
	s0= {q0}					s8= {q1, q3}
	s1={q1}					s9= {q2, q3}
	s2= {q2}					s10= {q0, q1, q2}
	s3= {q3}					s11= {q0, q2, q3}
	s4= {q0, q1}					s12= {q0, q1, q3}
	s5= {q0, q2}					s13= {q1, q2, q3}
	s6= {q0, q3}					s14= {q0, q1, q2, q3}
	s7= {q1, q2}					s15= Ø
	VERIFICAR OCORRÊNCIAS E ALINHAR CORRESPONDÊNCIAS
	δ		a	b	c	δ		a	b	c
	s0= {q0}		s4	s1	s15	s8= {q1, q3}		s15	s7	s3
	s1={q1}		s15	s7	s3	s9= {q2, q3}		s15	s15	s9
	s2= {q2}		s15	s15	s9	s10= {q0, q1, q2}		s4	s7	s9
	s3= {q3}		s15	s15	s15	s11= {q0, q2, q3}		s4	s1	s9
	s4= {q0, q1}		s4	s7	s3	s12= {q0, q1, q3}		s4	s7	s3
	s5= {q0, q2}		s4	s1	s3	s13= {q1, q2, q3}		s15	s7	s9
	s6= {q0, q3}		s4	s1	s15	s14= {q0, q1, q2, q3}		s4	s7	s9
	s7= {q1, q2}		s15	s7	s9	s15= Ø		s15	s15	s15
	ELIMINAR ESTADOS INALCANSÁVEIS
	δ		a	b	c	δ		a	b	c
	s0= {q0}		s4	s1	s15	s8= {q1, q3}		s15	s7	s3
	s1={q1}		s15	s7	s3	s9= {q2, q3}		s15	s15	s9
	s2= {q2}		s15	s15	s9	s10= {q0, q1, q2}		s4	s7	s9
	s3= {q3}		s15	s15	s15	s11= {q0, q2, q3}		s4	s1	s9
	s4= {q0, q1}		s4	s7	s3	s12= {q0, q1, q3}		s4	s7	s3
	s5= {q0, q2}		s4	s1	s3	s13= {q1, q2, q3}		s15	s7	s9
	s6= {q0, q3}		s4	s1	s15	s14= {q0, q1, q2, q3}		s4	s7	s9
	s7= {q1, q2}		s15	s7	s9	s15= Ø		s15	s15	s15
	MONTAR O AFD A PARTIR DE δ
	ELIMINAR ESTADOS SEM FINAL
	TESTAR PALAVRA AABCBAAC
	CICLO	t0	t1	t2	t3	t4	t5	t6	t7	t8
	ENTRADA	A	A	B	C	B	A	A	C	-
	ESTADO	s4	s4	s7	s9	-	-	-	s9	-
	RESULTADO:	ok!
Q3
	 A -> H1 H0		A -> 
	 | H2 H0
	 | H3 H0
	 | H0 H0
	 | ϵ
	 | c
	 B -> H4 C
	 | B H5
	 | A C
	 | b
	 | A B
	 | H1 H0
	 | H2 H0
	 | H3 H0
	 | H0 H0
	 | ϵ
	 | c
	 C -> c
	H0 -> a
	H1 -> H3 B
	H2 -> H0 B
	H3 -> B H0
	H4 -> A B
	H5 -> b
Q4
Q5
	Parte 1	Construir a tabela de transições do AFN (δ)
	δ	0	1
	q0	{q1}	{q0, q1}
	q1	{q0}	Ø
	Parte 2	Construir a tabela de transições para o AFD (δ) 
	δ	0	1
	S0 = {q0}
	S1 = {q1}
	S2 = {q0, q1}
	S3 = Ø
	Parte 3	Mostrar todos os conjuntos com estados finais
	δ	0	1
	S0 = {q0}
	S1 = {q1}
	S2 = {q0, q1}
	S3 = Ø
	Parte 4	Verificar ocorrencias e alinhar correspondencias
	δ	0	1
	S0 = {q0}	S1	S2
	S1 = {q1}	S0	S3
	S2 = {q0, q1}	S2	S2
	S3 = Ø	S3	S3
	Parte 5	Eliminar estados inalcansáveis 
	δ	0	1
	S0 = {q0}	S1	S2
	S1 = {q1}	S0	S3		Neste caso não existem.
	S2 = {q0, q1}	S2	S2
	S3 = Ø	S3	S3
	Parte 6	Montar o AFD a partir de (δ)
	Parte 7	Eliminar estados que não possuem saída para estados finais
	Parte 8	Teste com a palavra 01010010
	Ciclo	t0	t1	t2	t3	t4	t5	t6	t7	t8
	Entrada	0	1	0	1	0	0	1	0	-
	Estado	S1	S0	S1	S0	S1	S0	S2	S2	S2
		OK!