Quiz de Máquinas de Turing Determinísticas

Beschreibung

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 von Loys Gibertoni, aktualisiert more than 1 year ago
Loys Gibertoni
Erstellt von Loys Gibertoni vor etwa 9 Jahre
105
3

Zusammenfassung der Ressource

Frage 1

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

Frage 2

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

Frage 3

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

Frage 4

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

Frage 5

Frage
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?
Antworten
  • 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

Frage 6

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

Frage 7

Frage
Considerando a máquina de Turing da imagem, qual será o comportamento da máquina para as cadeias aaabbbccc, aaababccc e λ?
Antworten
  • Aceita, rejeita e aceita
  • Aceita, aceita e aceita
  • Rejeita, rejeita e rejeita
  • Aceita, rejeita e rejeita
  • Nenhuma das demais
Zusammenfassung anzeigen Zusammenfassung ausblenden

ähnlicher Inhalt

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