TEORIA DA COMPUTAÇÃO 5

Prévia do material em texto

Disc.: TEORIA DA COMPUTAÇÃO 
	2022.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.
		Se o estado inicial for também estado final em um autômato finito, então esse autômato
	
	
	
	não aceita a cadeia vazia.
	
	
	não tem outros estados finais.
	
	
	é não determinístico.
 
	
	
	aceita a cadeia vazia.
	
	
	é determinístico.
	
Explicação:
Quando o estado inicial também é final num AF, então ele aceita a cadeia vazia. 
	
	
	
	 
		
	
		2.
		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:
	
	
	
	Array
	
	
	Five elements
	
	
	Autômato quinto
	
	
	Mapeamento
	
	
	quíntupla
	
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).
	
	
	
	 
		
	
		3.
		Um automato finito é representado por um quintupla (Q, Ʃ, δ, q0, F) onde q0 representa 
 
	
	
	
	as transições
	
	
	os simbolos de entrada
	
	
	O número de estados
	
	
	o conjunto de estados finais
	
	
	o estado inicial
 
	
	
	 
		
	
		4.
		Um automato finito é representado por um quintupla (Q, Ʃ, δ, q0, F) onde F representa 
 
	
	
	
	o conjunto de estados finais
	
	
	as transições
	
	
	o estado inicial
 
	
	
	os simbolos de entrada
	
	
	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}
	
	
	
	 
		
	
		5.
		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?
 
	
	
	
	64
	
	
	16
	
	
	32
	
	
	128
 
	
	
	8
	
Explicação:
O cálculo é simples. Basta calcular 2 elevado ao número de estados do AFN: portanto 16 estados
	
	
	
	 
		
	
		6.
		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
	
	
	Grafos
	
	
	Autômatos Indeterminados
	
	
	Autômatos Finitos
	
	
	Autômatos Infinitos
	
Explicação:
Os Autômatos Finitos são facilmente descritas por expressões simples, chamadas Expressões Regulares.
	
	
	
	 
	 
	Não Respondida
	 
	 
	 Não Gravada
	 
	 
	Gravada
	
Exercício inciado em 21/04/2022 07:33:28.