AV 2 - TEORIA DA COMPUTAÇÃO

Prévia do material em texto

Disc.: TEORIA DA COMPUTAÇÃO Turma: 3001
Aluno: WELLINGTON FARIAS DA CONCEIÇÃO Matr.: 201908299851
Prof.: LUIS ALEXANDRE ESTEVAO DA SILVA Gabarito após: 09/11/2022 20:01
5840223322 08/11/2022 20:01:04
 
 1. Ref.: 7630092
Com base na Máquina de Turing abaixo, marque a alternativa cuja fita de entrada não será aceita.
 
112222
2222221
1121122
11122211
21111112
Respondido em 08/11/2022 20:33:48
 
 2. Ref.: 7703407
Qual o grau nó 4?
 
3
1
4
0
2
Respondido em 08/11/2022 20:34:25
 
 3. Ref.: 7703299
javascript:alert('C%C3%B3digo da quest%C3%A3o: 7630092.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 7703407.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 7703299.');
#######################
####$$$$$$############$$$$
$$$$$$$$$$$$$$$$$$$$$$$
######################
@@@@@@@
@@@@@@@@
###############
Marque a alternativa que contém uma entrada inválida para o Autômato apresentado na figura
abaixo:
1000111
01010101
10111
000000
11111
Respondido em 08/11/2022 20:34:30
 
 4. Ref.: 7703649
Assinale a alternativa que apresenta a Expressão Regular equivalente ao Autômato abaixo:
aba*
aba
a*b
aba**
a(ba)*
Respondido em 08/11/2022 20:34:43
 
 5. Ref.: 7630171
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
javascript:alert('C%C3%B3digo da quest%C3%A3o: 7703649.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 7630171.');
q0 - {q2, 2, R} -
q1 - {q0, 0, R} -
q2 - - -
q3 - - {q1, 1, R}
q4 {q5, 1, R} - -
q5 - {q3, 2, R} -
 
Respondido em 08/11/2022 20:35:24
 
 6. Ref.: 7629838
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 q2 -
estado A R
q0 - q1
q1 q2 -
q2 q3 -
q3 - q1
estado A B
q0 - q1
javascript:alert('C%C3%B3digo da quest%C3%A3o: 7629838.');
q1 q2 -
q2 - q3
q3 q2 -
estado A R
q0 - q1
q1 q2 -
q2 - {q1, q3}
q3 q2 -
estado A R
q0 - q1
q1 - q2
q2 q3 -
q3 - q3
Respondido em 08/11/2022 20:36:09
 
 7. Ref.: 7630133
Com base no Autômato Finito Determinístico abaixo, marque a alternativa que representa a sua expressão regular.
 
{anb | n >= 0}
{anbn | n >= 0}
{anbn | n >= 0 e m>= 0 }
{anbm | n >= 1 e m>= 0 }
{abn | n >= 0}
Respondido em 08/11/2022 20:36:37
 
 8. Ref.: 7648816
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 -
 
javascript:alert('C%C3%B3digo da quest%C3%A3o: 7630133.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 7648816.');
Respondido em 08/11/2022 20:38:38
 
 9. Ref.: 7755198
Marque a entrada inválida para a expressão regular x*yx*yx* : 
yxxxyxxxx
xxxxyxxxxyxxxx
xyxyx
yxyx
yyyyxyyyyy
Respondido em 08/11/2022 20:37:50
 
 10. Ref.: 7648821
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.
javascript:alert('C%C3%B3digo da quest%C3%A3o: 7755198.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 7648821.');
8
6
4
5
7
Respondido em 08/11/2022 20:37:20