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.
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 λ?