Quiz de Máquinas de Turing Determinísticas

Descrição

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.
Loys Gibertoni
Quiz por Loys Gibertoni, atualizado more than 1 year ago
Loys Gibertoni
Criado por Loys Gibertoni aproximadamente 9 anos atrás
104
3

Resumo de Recurso

Questão 1

Questão
Das alternativas abaixo, qual não pode ser resolvida por Máquina de Turing ?
Responda
  • 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

Questão 2

Questão
O modelo determinístico apresentado pelo grupo (modelo determinístico clássico) se diferencia dos demais por:
Responda
  • 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

Questão 3

Questão
A máquina de Turing é representada por:
Responda
  • 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

Questão 4

Questão
Qual das opções abaixo não é possível de se acontecer com uma máquina de Turing?
Responda
  • 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

Questão 5

Questão
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?
Responda
  • 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

Questão 6

Questão
A configuração de uma máquina de Turing é uma tripla. Quais elementos a compõe?
Responda
  • 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

Questão 7

Questão
Considerando a máquina de Turing da imagem, qual será o comportamento da máquina para as cadeias aaabbbccc, aaababccc e λ?
Responda
  • Aceita, rejeita e aceita
  • Aceita, aceita e aceita
  • Rejeita, rejeita e rejeita
  • Aceita, rejeita e rejeita
  • Nenhuma das demais

Semelhante

MBA Marketing - GERALZAO - PECEGE USP TURMA 171
Elaine Ferreira
Percepção
Henrique Zacarias
Química 1
Brunna Souza
Senso Comum e Ciência
Thaís Pontes
O Classicismo
Grazi_1
Química
Brunna Souza
BOTÂNICA
Danilo Righetto
Investigação Ação
Paulo Fochi
TBL Sandra Hipersensibilidade
Beatriz Moitinho
Automatos Limitados Linearmente
GRUPO 11
Classificação da constituição
Als Treinamentos