AV2 - TEORIA DA COMPUTAÇÃO

Prévia do material em texto

5840223322 A
01/11/2022 12:45
 
Nome: Matrícula: ________________
Disciplina: CCT0737 / TEORIA DA COMPUTAÇÃO Data: ___ /___ /______
Período: 2022.2 / AV2 Turma: 3001
 
 
Leia com atenção as questões antes de responder.
É proibido o uso de equipamentos eletrônicos portáteis e consulta a materiais de qualquer natureza durante a realização da prova.
Boa prova.
 
 
 
 
 
 
 
 
 
 
 
 
1. _______ de 1,00 
Com base na Máquina de Turing abaixo, marque a alternativa cuja fita de entrada não será aceita.
 
11122211
2222221
112222
1121122
21111112
2. _______ de 1,00 
Qual o grau nó 4?
 
4
2
3
1
0
3. _______ de 1,00 
Marque a alternativa que contém uma entrada inválida para o Autômato apresentado na figura
abaixo:
1000111
11111
01010101
10111
000000
4. _______ de 1,00 
Assinale a alternativa que apresenta a Expressão Regular equivalente ao Autômato abaixo:
aba
a*b
aba*
a(ba)*
aba**
5. _______ de 1,00 
Com base na matriz de transição da máquina de Turing abaixo, marque a alternativa que representa o autômato
correspondente.
estado 0 1 2
q0 - {q2, 2, R} -
q1 - {q0, 0, R} -
q2 - - -
q3 - - {q1, 1, R}
q4 {q5, 1, R} - -
q5 - {q3, 2, R} -
 
6. _______ de 1,00 
Com base no autômato finito deteminístico abaixo, marque a alternativa que represente a matriz de transição
correspondente a ele.
estado A R
q0 - q1
q1 q2 -
q2 q3 -
q3 - q1
estado A B
q0 - q1
q1 q2 -
q2 - q3
q3 q2 -
estado A R
q0 - q1
q1 - q2
q2 q3 -
q3 - q3
estado A R
q0 - q1
q1 q2 -
q2 - {q1, q3}
q3 q2 -
estado A R
q0 - q1
q1 q2 -
q2 - q3
q3 q2 -
7. _______ de 1,00 
Com base no Autômato Finito Determinístico abaixo, marque a alternativa que representa a sua expressão regular.
 
{anbn | n >= 0}
{abn | n >= 0}
{anbn | n >= 0 e m>= 0 }
{anbm | n >= 1 e m>= 0 }
{anb | n >= 0}
8. _______ de 1,00 
Considerando a tabela de transição de estado abaixo, marque a alternativa que represente o autômato equivalente.
Considere q0 como o estado inicial.
Estado a b
qo - q1
q1 q2 -
q2 - {q1, q3}
q3 q3 -
 
Campus:
NOVA AMÉRICA
Prova Impressa em 01/11/2022 por
LUIS ALEXANDRE ESTEVAO DA SILVA
 
Ref.: 5840223322 Prova Montada em 01/11/2022
9. _______ de 1,00 
Marque a entrada inválida para a expressão regular x*yx*yx* : 
yyyyxyyyyy
yxxxyxxxx
yxyx
xxxxyxxxxyxxxx
xyxyx
10. _______ de 1,00 
Com base na máquina de Turing abaixo e tendo a fita de entrada com a fita de entrada 'aababbb', quantas operações serão
realizadas para que o autômato seja aceito.
7
8
4
5
6