Quiz de Máquinas de Turing Determinísticas

Loys Gibertoni
Quiz by Loys Gibertoni, updated more than 1 year ago
Loys Gibertoni
Created by Loys Gibertoni about 6 years ago
86
3

Description

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.

Resource summary

Question 1

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

Question 2

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

Question 3

Question
A máquina de Turing é representada por:
Answer
  • 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

Question 4

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

Question 5

Question
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?
Answer
  • 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

Question 6

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

Question 7

Question
Considerando a máquina de Turing da imagem, qual será o comportamento da máquina para as cadeias aaabbbccc, aaababccc e λ?
Answer
  • Aceita, rejeita e aceita
  • Aceita, aceita e aceita
  • Rejeita, rejeita e rejeita
  • Aceita, rejeita e rejeita
  • Nenhuma das demais
Show full summary Hide full summary

Similar

MBA Marketing - GERALZAO - PECEGE USP TURMA 171
Elaine Ferreira
Química 1
Brunna Souza
Percepção
Henrique Zacarias
Percepção
Rebecca Viana
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
Classificação da constituição
Als Treinamentos