CCT0832_AV_1

Prévia do material em texto

TEORIA DA COMPUTAÇÃO
	 
	 
	 1.
	Ref.: 3555877
	Pontos: 1,00  / 1,00
	
	É possível definir o conceito de linguagem como:
		
	
	Qualquer número de símbolos
	
	Um conjunto finito de símbolos.
	
	Uma sequência finita de símbolos.
	 
	Um conjunto de palavras sobre um alfabeto.
	
	Resoluções de problemas envolvendo o processamento de dados.
	
	
	 2.
	Ref.: 3555883
	Pontos: 1,00  / 1,00
	
	Se precisarmos representar/armazenar um grafo em um computador, uma das estruturas mas comumentes utilizada é:
		
	
	Grafo Euleriano
	
	Matriz proporcional
	
	Grafo Bipartido
	
	Matriz Inversa
	 
	Matriz de adjacência
	
	
	 3.
	Ref.: 3555933
	Pontos: 1,00  / 1,00
	
	Trantando-se de propriedade em árvores, a maior distância entre qualquer par de vértices é denominado:
		
	
	Raio
	
	Raiz
	 
	Diâmetro
	
	Base
	
	Centro
	
	
	 4.
	Ref.: 3557621
	Pontos: 0,00  / 1,00
	
	O funcionamento do automato é definido pelo(a)
		
	
	Conjunto de Saida
	 
	Função de Transição
	
	Conjunto dos Estados
	 
	Entrada Realizada
 
	
	Ligação da entrada
	
	
	 5.
	Ref.: 3557636
	Pontos: 1,00  / 1,00
	
	Considere a seguinte informação de um quintupla de um automato não deterministico
Q = {q0, q1, q2 }
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 ?
		
	
	3
	
	6
	
	2
	
	4
	 
	8
	
	
	 6.
	Ref.: 3563592
	Pontos: 1,00  / 1,00
	
	a operação regular unária é a :
		
	
	DIFERENÇA
	
	UNIÃO
	
	INTERSECÇÃO
	
	CONCATENAÇÃO
 
	 
	ESTRELA
	
	
	 7.
	Ref.: 3557882
	Pontos: 1,00  / 1,00
	
	O autômato finito determinístico com saídas associadas aos estados, só que nesse caso as saídas são produzidas por uma função que determina esta saída (podendo também ser vazia) determinando o estado da máquina denomina-se.
		
	
	Máquina de Church
	
	Maquina de Turing
	 
	Maquina de Moore
	
	Máquina de Kleene
 
	
	Máquina de Estados Finitos
	
	
	 8.
	Ref.: 3557880
	Pontos: 1,00  / 1,00
	
	Dentre as teoria dos automatos a mais abrangente é :
		
	
	O  Automato Finito
	
	A  Máquina de Estados Finitos
 
	 
	A  Maquina de Turing
	
	O  Automato de Pilha
	
	A  Lógica Combinacional
	
	
	 9.
	Ref.: 3563164
	Pontos: 1,00  / 1,00
	
	Considere a seguinte gramática G, onde S é o símbolo inicial:
SABA→AcB→cA|aB→cB|aA→ε
Assinale a alternativa que apresenta a palavra que NÃO pertence à linguagem gerada pela gramática G.
 
		
	
	ccac
 
	
	aaaca
 
	
	aaca
 
	
	 ccca
 
	 
	aaa
	
	
	 10.
	Ref.: 3557849
	Pontos: 0,00  / 1,00
	
	Um problema NP Completo é aquele que :
		
	 
	Não pode ser resolvido em tempo polinomial
	
	Possui solução computacional possível em um tempo aceitavel
	
	Cresce linearmente em função do volume de dados de entrada
	 
	É resolvido em tempo polinomial
	
	Pertence a classe de toda as linguagens polinomialmente decidíveis