Quiz de Máquinas de Turing Determinísticas

Question 1 of 7

1

Das alternativas abaixo, qual não pode ser resolvida por Máquina de Turing ?

Select one of the following:

Verificar se a parentisação de uma expressão está correta
Dizer se dois códigos diferentes são equivalentes
Contar o tamanho de uma string
Reconhecer gramáticas regulares

Explanation

Question 2 of 7

1

O modelo determinístico apresentado pelo grupo (modelo determinístico clássico) se diferencia dos demais por:

Select one of the following:

Limitar apenas a parte esquerda da fita
Limitar tanto a parte esquerda quanto a parte direita da fita
Usar múltiplas fitas
Permitir que a cabeça de leitura permaneça parada

Explanation

Question 3 of 7

1

A máquina de Turing é representada por:

Select one of the following:

Uma máquina de estados finita
Uma memória em pilha
Um conjunto de funções de transição, fita e cabeça de leitura e escrita
Uma linguagem de programação orientada a objetos

Explanation

Question 4 of 7

1

Qual das opções abaixo não é possível de se acontecer com uma máquina de Turing?

Select one of the following:

Aceitar uma cadeia de entrada ou rejeitá-la
Ficar em loop e nunca parar
Usar a fita como saída quando se a utiliza para processamento de funções e procedimentos
Determinar que uma entrada é inválida sem sequer lê-la

Explanation

Question 5 of 7

1

De acordo com a definição formal de máquina de Turing, quantos elementos são necessários para representá-la e quais são eles?

Select one of the following:

A máquina é uma quádrupla composta de:
1. Conjunto de símbolos não terminais
2. Conjunto de símbolos terminais
3. Conjunto de regras de produção
4. Axioma
A máquina é uma quíntupla:
1. Conjunto de estados
2. Alfabeto de entrada
3. Função de transição
4. Estado inicial
5. Conjunto de estados finais
A máquina é uma tripla:
1. Estado inicial
2. Conteúdo inicial da fita
3. Posição inicial da cabeça de leitura
A máquina é uma sétupla:
1. Conjunto de estados
2. Alfabeto da entrada
3. Alfabeto da fita
4. Função de transição
5. Estado inicial
6. Estado de aceitação
7. Estado de rejeição

Explanation

Question 6 of 7

1

A configuração de uma máquina de Turing é uma tripla. Quais elementos a compõe?

Select one of the following:

Estado atual, conteúdo atual da fita e posição atual
Número de fitas ativas, status de aceitação atual e estado atual
Estado atual, direção de leitura e posição atual
Estado atual, número de leituras realizadas e conteúdo atual

Explanation

Question 7 of 7

1

Considerando a máquina de Turing da imagem, qual será o comportamento da máquina para as cadeias aaabbbccc, aaababccc e λ?

Select one of the following:

Aceita, rejeita e aceita
Aceita, aceita e aceita
Rejeita, rejeita e rejeita
Aceita, rejeita e rejeita
Nenhuma das demais

	Created by Loys Gibertoni about 9 years ago

	Copied by Weverton Sullivan over 7 years ago

Um divertido quiz sobre máquinas de Turing determinísticas para o trabalho 3 da disciplina SCC-205 - Teoria da Computação e Linguagens Formais do ano de 2015.

Quiz de Máquinas de Turing Determinísticas

Question 1 of 7

Das alternativas abaixo, qual não pode ser resolvida por Máquina de Turing ?

Select one of the following:

Explanation

Question 2 of 7

O modelo determinístico apresentado pelo grupo (modelo determinístico clássico) se diferencia dos demais por:

Select one of the following:

Explanation

Question 3 of 7

A máquina de Turing é representada por:

Select one of the following:

Explanation

Question 4 of 7

Qual das opções abaixo não é possível de se acontecer com uma máquina de Turing?

Select one of the following:

Explanation

Question 5 of 7

De acordo com a definição formal de máquina de Turing, quantos elementos são necessários para representá-la e quais são eles?

Select one of the following:

Explanation

Question 6 of 7

A configuração de uma máquina de Turing é uma tripla. Quais elementos a compõe?

Select one of the following:

Explanation

Question 7 of 7

Considerando a máquina de Turing da imagem, qual será o comportamento da máquina para as cadeias aaabbbccc, aaababccc e λ?

Select one of the following:

Explanation