Copia de Lista 3 - Formais

Prévia do material em texto

Departamento de Ciência da Computação - DCC/UFBA 
MATA50 - Linguagens Formais e Autômatos 2020.1 - SLS 
Professor: Marlo Souza
Discentes: André Luiz Gomes, Diego Carapiá, Fábio Castro, Matheus Novais
Grupo B - Lista 3
1. 
a) #states
s0
s1
s2
s3
s4
#initial
s0
#accepting
s4
#alphabet
a
b
#transitions
s0:a>s1
s0:b>s0
s1:a>s1
s1:b>s2
s2:a>s1
s2:b>s3
s3:a>s4
s3:b>s0
s4:a>s4
s4:b>s4
b) #states
s0
s1
s2
s3
#initial
s0
#accepting
s0
#alphabet
a
b
#transitions
s0:a>s1
s0:b>s0
s1:a>s3
s1:b>s2
s2:a>s3
s2:b>s0
s3:a>s3
s3:b>s3
b) Diego
#states
N
s0
s1
s2
#initial
s0
#accepting
s0
s1
s2
#alphabet
a
b
#transitions
s0:a>N
N:a>N
N:b>N
s0:b>s1
s1:a>N
s1:b>s2
s2:a>s0
s2:b>s2
c) #states
a0b0
a0b1
a1b1
a2b1
a3b1
a4b1
a1b0
a2b0
a3b0
a4b0
#initial
a0b0
#accepting
a0b0
#alphabet
a
b
#transitions
a0b0:a>a1b0
a0b0:b>a0b1
a0b1:a>a1b1
a0b1:b>a0b0
a1b1:a>a2b1
a1b1:b>a1b0
a2b1:a>a3b1
a2b1:b>a2b0
a3b1:a>a4b1
a3b1:b>a3b0
a4b1:a>a0b0 (a4b1:a>a0b1)
a4b1:b>a4b0
a1b0:a>a2b0
a1b0:b>a1b1
a2b0:a>a3b0
a2b0:b>a2b1
a3b0:a>a4b0
a3b0:b>a3b1
a4b0:a>a0b0
a4b0:b>a4b1
d) #states
s0
s1
s2
s3
s4
s5
s6
s7
s8
s9
s10
s11
s12
s13
s14
#initial
s0
#accepting
s4
s7
s11
s14
#alphabet
a
b
#transitions
s0:a>s1
s1:a>s2
s2:a>s3
s2:b>s2
s3:a>s4
s3:b>s2
s4:a>s4
s4:b>s2
s1:b>s5
s5:a>s6
s5:b>s5
s6:b>s7
s6:a>s6
s7:a>s6
s7:b>s5
s0:b>s8
s8:b>s9
s9:b>s10
s9:a>s9
s10:a>s9
s10:b>s11
s11:b>s11
s11:a>s9
s8:a>s12
s12:b>s13
s12:a>s12
s13:a>s14
s13:b>s13
s14:a>s12
s14:b>s13
2. 
#states
s0
s1
s2
s3
s4
#initial
s0
#accepting
s0
#alphabet
0
1
#transitions
s0:0>s0
s0:1>s1
s1:0>s2
s1:1>s3
s2:0>s4
s2:1>s0
s3:0>s1
s3:1>s2
s4:0>s3
s4:1>s4
Questão Extra
a)
#states
000
D000
D001
C010
D010
C011
C100
D100
D101
D110
C111
#initial
000
#accepting
D000
D001
D010
D100
D101
D110
#alphabet
A
B
#transitions
000:A>C100
000:B>C011
D000:A>C100
D000:B>C011
D001:A>C111
D001:B>D000
C010:A>C100
C010:B>D001
D010:A>C100
D010:B>D001
C011:A>C100
C011:B>D010
C100:A>C010
C100:B>C111
D100:A>C010
D100:A>C111
D101:A>C011
D101:B>D100
D110:A>D000
D110:B>D101
C111:A>D001
C111:B>D110
b)
	x1 x2 x3
	A
	B
	-> 000
	C - 100
	C - 011
	 *D - 000
	C - 100
	C - 011
	* D - 001
	C - 111
	*D - 000
	C - 010 ou *D - 010
	C - 100
	*D - 001
	C - 011
	C - 100
	*D - 010
	 C - 100 ou *D - 100
	C - 010
	C - 111
	*D - 101
	C - 011
	*D - 100
	*D - 110
	*D - 000
	*D - 101
	C - 111
	*D - 001
	*D -110
Os estados são representados pela posição de cada chave(x1,x2,x3) sendo 0 quando a chave está para esquerda e 1 quando a chave está para direita e pela saída que pode ser C ou D. A saída depende unicamente das posições da chave. 
As entradas podem ser A ou B, que indicam onde a bolinha foi solta, essas entradas modificam o estado como mostrado na tabela acima.
c) Nas questões a e b, a saída da bolinha era calculada baseada no estado anterior as entradas A ou B. Se as alavancas fossem computadas antes, poderia mudar o primeiro dígito do meu estado, que indica onde a bolinha saiu. Esse cálculo seria baseado no estado futuro das posições. Exemplo: anteriormente δ(D000,B) = C011 (000 com B cai em C). Agora δ(D000,B) = D011 (000 com B se transforma em 011 que cai em D).