Autômatos Finitos e Conversão

Prévia do material em texto

04/06/2020 EPS
simulado.estacio.br/alunos/ 1/3
 
 
 
 TEORIA DA COMPUTAÇÃO
5a aula
 Lupa 
PPT MP3
 
Exercício: CCT0832_EX_A5_201908040459_V3 10/04/2020
Aluno(a): JOSEILDON DA SILVA DANTAS 2020.1 EAD
Disciplina: CCT0832 - TEORIA DA COMPUTAÇÃO 201908040459
 
 1a Questão
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?
 
 128
 
64
 16
8
32
Respondido em 10/04/2020 07:35:31
Explicação:
O cálculo é simples. Basta calcular 2 elevado ao número de estados do AFN: portanto 16 estados
 
 2a Questão
Um automato finito é representado por um quintupla (Q, Ʃ, δ, q0, F) onde F representa 
 
 os simbolos de entrada
o estado inicial
 
 o conjunto de estados finais
O número de estados
as transições
Respondido em 10/04/2020 07:35:21
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
http://simulado.estacio.br/alunos/inicio.asp
javascript:voltar();
javascript:diminui();
javascript:aumenta();
javascript:abre_frame('2','5','','','');
javascript:abre_frame('3','5','','','');
04/06/2020 EPS
simulado.estacio.br/alunos/ 2/3
 δ (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}
 
 3a Questão
Se o estado inicial for também estado final em um autômato finito, então esse autômato
 aceita a cadeia vazia.
não aceita a cadeia vazia.
é não determinístico.
 
é determinístico.
não tem outros estados finais.
Respondido em 10/04/2020 07:35:24
Explicação:
Quando o estado inicial também é final num AF, então ele aceita a cadeia vazia. 
 
 4a Questão
Um automato finito é representado por um quintupla (Q, Ʃ, δ, q0, F) onde q0 representa 
 
 o conjunto de estados finais
os simbolos de entrada
O número de estados
as transições
 o estado inicial
 
Respondido em 10/04/2020 07:35:26
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}
 
 5a Questão
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:
 Autômato quinto
Mapeamento
Array
Five elements
04/06/2020 EPS
simulado.estacio.br/alunos/ 3/3
 quíntupla
Respondido em 10/04/2020 07:35:29
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).
 
 6a Questão
Constituem um conjunto de linguagens decidíveis bastante simples e com propriedades bem definidas e compreendidas. Está é
uma característica encontrada nos:
 Árvores Binária
Autômatos Indeterminados
Autômatos Infinitos
Grafos
 Autômatos Finitos
Respondido em 10/04/2020 07:35:31
Explicação:
Os Autômatos Finitos são facilmente descritas por expressões simples, chamadas Expressões Regulares.
javascript:abre_colabore('38403','185604852','3701118088');