Teoria da Computação - TESTE 5

Prévia do material em texto

04/05/2021 Estácio: Alunos
https://simulado.estacio.br/alunos/?p0=33848280&user_cod=3070659&matr_integracao=202008191076 1/3
Teste de
Conhecimento
 avalie sua aprendizagem
Constituem um conjunto de linguagens decidíveis bastante simples e com propriedades bem definidas e compreendidas.
Está é uma característica encontrada nos:
Se o estado inicial for também estado final em um autômato finito, então esse autômato
A definição formal diz que um autômato finito é uma lista de cinco objetos: conjunto de estados, alfabeto de entrada,
regras para movimentação, estado inicial, e estados de aceitação. Essa lista de cinco elementos é frequentemente
chamada:
TEORIA DA COMPUTAÇÃO 
Lupa Calc.
 
 
CCT0832_A5_202008191076_V1 
Aluno: YURI CID DA SILVA LIMA Matr.: 202008191076
Disc.: TEORIA DA COMPUTAÇÃO 2021.1 EAD (G) / EX
Prezado (a) Aluno(a),
 
Você fará agora seu TESTE DE CONHECIMENTO! Lembre-se que este exercício é opcional, mas não valerá ponto para sua
avaliação. O mesmo será composto de questões de múltipla escolha.
Após responde cada questão, você terá acesso ao gabarito comentado e/ou à explicação da mesma. Aproveite para se
familiarizar com este modelo de questões que será usado na sua AV e AVS.
 
1.
Árvores Binária
Autômatos Finitos
Autômatos Infinitos
Autômatos Indeterminados
Grafos
Explicação:
Os Autômatos Finitos são facilmente descritas por expressões simples, chamadas Expressões Regulares.
 
 
2.
é determinístico.
não tem outros estados finais.
é não determinístico.
 
não aceita a cadeia vazia.
aceita a cadeia vazia.
Explicação:
Quando o estado inicial também é final num AF, então ele aceita a cadeia vazia. 
 
 
3.
Five elements
javascript:voltar();
javascript:voltar();
javascript:diminui();
javascript:aumenta();
javascript:calculadora_on();
04/05/2021 Estácio: Alunos
https://simulado.estacio.br/alunos/?p0=33848280&user_cod=3070659&matr_integracao=202008191076 2/3
Um automato finito é representado por um quintupla (Q, Ʃ, δ, q0, F) onde q0 representa 
 
Um automato finito é representado por um quintupla (Q, Ʃ, δ, q0, F) onde F representa 
 
Array
quíntupla
Autômato quinto
Mapeamento
Explicação:
Dizemos que um autômato finito é representado por uma quíntupla (Q, Ʃ, δ, q0, F), onde Q é o conjunto finito de estados, Ʃ é
o conjunto finito de símbolos de entrada, δ é a função de transição, q0 é o estado inicial (q0 ∈ Q o estado inicial é apontado
por uma seta) e F o conjunto de estados finais ou de aceitação (os estados de aceitação são apontados por um círculo dentro
de outro ou asterisco e um estado inicial também pode ser final).
 
 
4.
o conjunto de estados finais
as transições
os simbolos de entrada
O número de estados
o estado inicial
 
Explicação:
Seguindo a propriedade de um autômato finito que é representado por uma quíntupla (Q, Ʃ, δ, q0, F):
 Q = número de estados = {q0, q1, q2, q3}
 Ʃ = símbolos de entrada = {0,1}
 δ = transições = 
 δ (q0, 0) = q2
 δ (q0, 1) = q1
 δ (q1, 0) = q3
 δ (q1, 1) = q0
 δ (q2, 0) = q0
 δ (q2, 1) = q3
 δ (q3, 0) = não possui = Ø (vazio)
 δ (q3, 1) = q2
 q0 = estado inicial = {q0}
 F = conjunto de estados finais = {q0}
 
 
5.
os simbolos de entrada
o conjunto de estados finais
o estado inicial
 
as transições
O número de estados
Explicação:
Seguindo a propriedade de um autômato finito que é representado por uma quíntupla (Q, Ʃ, δ, q0, F):
 Q = número de estados = {q0, q1, q2, q3}
 Ʃ = símbolos de entrada = {0,1}
 δ = transições = 
 δ (q0, 0) = q2
 δ (q0, 1) = q1
 δ (q1, 0) = q3
 δ (q1, 1) = q0
 δ (q2, 0) = q0
 δ (q2, 1) = q3
 δ (q3, 0) = não possui = Ø (vazio)
 δ (q3, 1) = q2
 q0 = estado inicial = {q0}
 F = conjunto de estados finais = {q0}
04/05/2021 Estácio: Alunos
https://simulado.estacio.br/alunos/?p0=33848280&user_cod=3070659&matr_integracao=202008191076 3/3
Seja um Autômato Finito Não Determinístico (AFN) com 4 estados. Aplicando-se o algoritmo de conversão de um AFN para
um Autômato Finito Determinístico (AFD), em quantos estados, no máximo, resultaria o AFD considerando-se os estados
inúteis?
 
 
 
6.
32
64
16
8
128
 
Explicação:
O cálculo é simples. Basta calcular 2 elevado ao número de estados do AFN: portanto 16 estados
 
 Não Respondida Não Gravada Gravada
 
 
Exercício inciado em 04/05/2021 12:24:10. 
 
 
 
 
javascript:abre_colabore('34697','224394855','4539918797');