1 TAREFA DE CASA _LISTA DE EXERCÍCIOS _Linguagens Formais e Automatos

Prévia do material em texto

1ª TAREFA DE CASA - LISTA DE EXERCÍCIOS – Valor: 5,00 pontos 
 
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 antes da aula. Ao iniciar a aula, 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: 30/11/2022 
f) Valor: 5,00 pontos 
 
 
1. Construa expressão regular, gramática regular e autômato finito sobre o alfabeto 
{@,#,$,%}das seguintes linguagens: 
 
a) A palavra inicia com @ e termina com $. 
b) A palavra finaliza com % ou # 
c) A palavra inicia com % ou $ 
d) A palavra possui como subpalavra @ ou $ 
e) A palavra possui como prefixo @ ou $ 
f) A palavra possui como sufixo # ou % 
g) A palavra possui como subpalavra $ ou # 
h) A palavra como prefixo # ou $ ou % 
 
2. Considere o Autômato Finito abaixo e responda: 
 
a) Verifica se as palavras são reconhecidas pelo autômato: abbaabb e 
bbabababa e construir a EXPRESSÃO REGULAR e relatar se o 
autômato é Autômato Finito Determinístico ou Autômato Finito Não 
Determinístico. 
 
 
 
b) Verifica se as palavras são reconhecidas pelo autômato: abbaab e 
bbababaaa e construir a EXPRESSÃO REGULAR e relatar se o autômato é 
Autômato Finito Determinístico ou Autômato Finito Não Determinístico. 
q0 q1 q2 qf
a a a
a, b
 
c) Verifica se as palavras são reconhecidas pelo autômato: 10011010 e 
100101 e construir a EXPRESSÃO REGULAR e relatar se o autômato é 
Autômato Finito Determinístico ou Autômato Finito Não Determinístico. 
 
 
d) Verifica se as palavras são reconhecidas pelo autômato: 1001101 e 
100100 e construir a EXPRESSÃO REGULAR e relatar se o autômato é 
Autômato Finito Determinístico ou Autômato Finito Não Determinístico. 
 
 
3. Escreva a expressão regular dos autômatos abaixo: 
 
a. 
 
b. 
 
c. 
 
d. 
 
e. 
 
f. 
 
 
 
 
 
 
 
 
 
 
 
4. Derivar as palavras abaixo de acordo com as gramáticas abaixo. 
a. 
A→ aS | bS | B 
B→ bC | dC 
C→ dC | bC | aC | λ 
Palavras: 
aabbdaaadddb 
babadddbaaba 
b. 
Z→#Z | $Z | W 
W→%P | #P 
P→%P | λ 
Palavras: 
%%%%%% 
#$#$% 
c. 
R→1S | 2S | 3S 
S→ 11T | 33T 
T→2T | 3T | λ 
Palavras 
12321232121123 
1232233 
d. 
X→ aB | bB 
B→ aaC | BBC 
C→ aC | bC | λ 
Palavras 
abababbbaaa 
babababbaa 
 
 
 5. 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}, F = {q2} 
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 entrada do Autômato de Pilha 
a. 012210 
b. 22 
c. 01022001 
d. 01022010 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 6. Considere a seguinte máquina de Turing: 
 
 
 Indique o traço de execução para cada uma das seguintes cadeias de entrada: 
(i) aaa (ii) aba (iii) baaba