2ª TAREFA DE CASA LISTA DE EXERCÍCIOS – LINGUAGENS FORMAIS E AUTOMATOS 6SINA 13 12 18 (1)

Prévia do material em texto

2ª TAREFA DE CASA - LISTA DE EXERCÍCIOS – Autômatos 
 
Observações. Leia antes de iniciar suas atividades. 
a) A Tarefa de Casa é Individual. Tarefa em grupos será pontuada nota Zero. 
b) A Tarefa deverá ser entregue em sala de aula, logo após o inicio da mesma. 
Depois, não será mais pontuada. 
c) Não será permitida a entrega por email ou fora do prazo. 
d) Só será aceita a Tarefa de Casa, se a mesma for MANUSCRITA. Em outros 
formatos será atribuída nota Zero. 
e) Data da entrega: 13/12/2018 
 
 
1. Sejam os conjuntos sobre o  = {0,1,2,3,4,5,6}. X = {0,1,2,3}, Y={3,4,5} e 
Z={0,2,3,5,6}. Construa a EXPRESSÃO REGULAR e GRAMÁTICA 
REGULAR dos resultados dos conjuntos abaixo: 
a) Conjunto: (X  Y)C  Z. Pede-se: A palavra formada pelo resultado do 
conjunto sempre inicia 52 e sempre finaliza com 30. 
b) Conjunto: (X  Z)  YC. Pede-se: A palavra formada pelo resultado do 
conjunto possui como subpalavra 02 ou 16. 
c) Conjunto: (Z  Y)  X. Pede-se: A palavra formada pelo resultado do 
conjunto possui como sufixo 5. 
 
2. Considere o Autômato Finito Determinístico e Autômato Finito não- 
Determinístico abaixo e responda: 
a) Determinar as derivações das palavras. abbaabb e bbabababa e construir 
a expressão regular do autômato. 
 
b) Determinar as derivações das palavras. abbaab e bbababaaa e construir a 
expressão regular do autômato. 
 
q0 q1 q2 qf
a a a
a, b
 
 
 
 
 
 
 
c) Determinar as derivações das palavras. 10011010 e 100101 e construir a 
expressão regular do autômato. 
 
 
 
d) Determinar as derivações das palavras. 1001101 e 100100 e construir a 
expressão regular do autômato. 
 
 
e) Determinar as derivações das palavras. 1001101 e 100100 e construir a 
expressão regular do autômato. 
 
 
 
 
3. Verificar se as palavras abaixo são reconhecidas pelo Autômato de Pilha a partir 
das seguintes Funções de Transição 
 = {0,1,2}* , Q = {q0, q1,q2} , Γ = {0 , 1}, q0, F = {q2}, Pilha = Vazia 
Função de Transição (δ) 
1) δ (q0 , 0 , 

 ) = { (q0, 0 ) } 
2) δ (q0 , 1 , 

 ) = { (q0, 1 ) } 
3) δ (q0 , 0 , 0 ) = { (q0, 00 ) } 
4) δ (q0 , 0 , 1 ) = { (q0, 01 ) } 
5) δ (q0 , 1 , 0 ) = { (q0, 10 ) } 
6) δ (q0 , 1 , 1 ) = { (q0, 11 ) } 
7) δ (q0 , 2 , 

 ) = { (q1, 

) } 
8) δ (q0 , 2 , 0 ) = { (q1, 0 ) } 
9) δ (q0 , 2 , 1 ) = { (q1, 1 ) } 
10) δ (q1 , 2 , 

 ) = { (q2, 

) } 
11) δ (q1 , 2 , 0 ) = { (q2, 0 ) } 
12) δ (q1 , 2 , 1 ) = { (q2, 1 ) } 
13) δ (q2 , 0 , 0 ) = { (q2, 

 ) } 
14) δ (q2 , 1 , 1 ) = { (q2, 

 ) } 
 
Testar as seguintes entradas do Autômato de Pilha 
a. 012210 
b. 22 
c. 01022001 
 
 
 
 
4. Considere a seguinte máquina de Turing: 
 
 
 
 
A partir da Máquina de Turing (MT) do exemplo, teste as seguintes entradas. 
a) ab 
b) aaabbb 
c) abab