Prova 2 2009

Prévia do material em texto

INF 331 - Prova 2 
 
Sejam 
),,,,( 111111 FqQM 
 e 
),,,,( 222222 FqQM 
 dois autômatos finitos 
determinísticos. Para construir um autômato 
),,,,( 333333 FqQM 
 que aceite a linguagem 
)()( 21 MLML 
, pode-se seguir os seguintes passos: 
 
213 QQQ 
, isto é, os estados de 
3M
 são formados por pares de estados, sendo o 
primeiro componente de 
1Q
, e o segundo componente de 
2Q
. 
 
213 
 
 
 213 ,qqq 
, isto é, o estado inicial de 
3M
 é formado por um par onde o primeiro 
componente é o estado inicial de 
1M
 e o segundo componente é o estado inicial de
2M
. 
 
213 FFF 
, isto é, os estados finais são os pares de estados que são finais em 
1M
 e 
2M
. 
 
       asarasr ,,,,, 213  
, para 
321 ,,  aQsQr
; se 
 ar,1
 ou 
 as,2
 
forem indefinidos, então 
  asr ,,3
 também é indefinido. 
Por exemplo, considere os autômatos finitos 
1M
 e 
2M
 abaixo: 
(
1M
) 
 
(
2M
) 
 
Um autômato 
3M
, que aceita uma linguagem que é a interseção entre 
)( 1ML
 e 
)( 2ML
, começou 
a ser construído abaixo: 
(
3M
) 
 
 O estado inicial é [1,3], par formado pelos estados 
iniciais de 
1M
 e 
2M
. 
 [1,3] é final porque 1 e 3 são ambos finais. 
 
         3,2,3,,1,3,1 213  aaa 
 
 
(A) Escreva expressões regulares que descrevem a linguagem 
)( 1ML
 e a linguagem 
)( 2ML
. 
(B) Descreva, em português, como são as palavras das linguagens 
)( 1ML
 e 
)( 2ML
. 
(C) Utilize o algoritmo apresentado acima para terminar a construção do autômato 
3M
. 
(D) Escreva uma expressão regular que descreve a linguagem 
)( 3ML
. 
(E) Escreva uma gramática regular que descreve a linguagem 
)( 3ML
. 
(F) Usando transições l, construa um autômato 
4M
 que aceita a linguagem 
)()( 21 MLML 
. 
(G) Construa um autômato determinístico 
5M
 equivalente a 
4M
. 
(H) Construa um autômato de pilha que aceita a linguagem 
zyx cba
 tal que 
// yxz 
 (o valor 
de z é o módulo da diferença entre x e y). Exemplos de palavras que devem ser aceitas: aaabcc, 
aaaccc, abbbcc, bbbccc. 
 
Pontuação: (A) = 4 pontos; (B) = 2 pontos; (C) = 7 pontos; (D) = 5 pontos; (E) = 5 pontos; 
(F) = 2 pontos; (G) = 7 pontos; (H) = 8 pontos