Exercício 4

Prévia do material em texto

Disc.: TEORIA DA COMPUTAÇÃO 2022.3 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. Quanto aos automatos deterministicos podemos afirmar que:
Pode estar em muitos estados ao mesmo tempo.
Para cada estado e para cada entrada só há zero ou uma transição possível
Não é representado por uma quíntupla
Para todo estado e todo símbolo de entrada sempre há 0 ou 1 ou n transições possíveis.
É um autômato que permite zero, uma ou mais transições a partir de um estado e para um mesmo
símbolo de entrada.
Explicação:
Um autômato finito determinístico é um autômato onde para cada estado e para cada entrada só há zero
ou uma transição possível
2. Um autômato finito determinístico , também chamado máquina de estados finita determinística (AFD),
é uma Máquina de estados finita que aceita ou rejeita cadeias de símbolos gerando um único ramo de
computação para cada cadeia de entrada. É uma de suas propriedades:
Para todo estado e todo símbolo de entrada sempre há zero ou uma transição possível.
Contém diversos números infinito de estados
Há tabelas de transição
Suas transições são incompletas
Para todo estado e todo símbolo de entrada sempre há zero ou uma ou n transições possíveis.
Explicação:
Um autômato finito tem um conjunto de estados, alguns dos quais são denominados estados finais. À
medida que caracteres da string de entrada são lidos, o controle da máquina passa de um estado a outro,
segundo um conjunto de regras de transição especificadas para o autômato.
https://simulado.estacio.br/bdq_simulados_exercicio.asp
https://simulado.estacio.br/bdq_simulados_exercicio.asp
3. Um automato finito é representado por um quintupla (Q, Ʃ, δ, q0, F) onde Q representa
o conjunto de estados finais
os simbolos de entrada
o estado inicial
O número de estados
as transições
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}
4. Uma das formas de representação do autômato finito indeterminístico mais comum é:
Setas
Matriz
Símbolo
Conjunto
Diagrama
Explicação:
.
https://simulado.estacio.br/bdq_simulados_exercicio.asp
https://simulado.estacio.br/bdq_simulados_exercicio.asp
5. Um automato finito é representado por um quintupla (Q, Ʃ, δ, q0, F) onde Ʃ representa
o conjunto de estados finais
o estado inicial
os simbolos de entrada
O número de estados
as transições
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}
6. Os movimentos realizado pelos automatos finitos constituem :
O conjunto de transições
O estado final
Os dados representados
O controle
O conjunto de estados
Explicação:
Conjunto de transições: movimentos possíveis de um estado para outro
https://simulado.estacio.br/bdq_simulados_exercicio.asp
https://simulado.estacio.br/bdq_simulados_exercicio.asp