Automatos Limitados Linearmente

Descripción

Quiz de linguagens formais
GRUPO 11
Test por GRUPO 11, actualizado hace más de 1 año
GRUPO 11
Creado por GRUPO 11 hace más de 8 años
128
0

Resumen del Recurso

Pregunta 1

Pregunta
O que difere uma Máquina de Turing (MT) para um Autômato Linearmente Limitado (ALL)?
Respuesta
  • A MT é ilimitada e o ALL é limitado. Apenas o ALL é incapaz de passar o(s) limite('s) da fita.
  • A MT possui uma fita ilimitada e preenche os espaços em branco do lado direito, enquanto o ALL tem uma fita limitada e não é capaz de sair desse espaço restrito.
  • O ALL é mais poderoso que a MT completa

Pregunta 2

Pregunta
Quais são os possíveis resultados de uma linguagem ALL quando se testa uma cadeia de entrada?
Respuesta
  • Aceitação, pois a linha segue as regras da linguagem, ou rejeição, pois não chegou no final do processo.
  • Aceitação, pois a linha segue as regras da linguagem, ou rejeição, pois não segue as regras da linguagem, ou loop, pois se repete elementos do alfabeto.
  • Aceitação, pois a cadeia segue as regras da linguagem, ou rejeição, pois não segue as regras da linguagem, ou loop, pois a linguagem entra em uma configuração que já esteve antes. Nesse último caso, toma-se a decisão de rejeitar.

Pregunta 3

Pregunta
Os ALL's são máquinas reconhecedoras de quais tipos de linguagens?
Respuesta
  • Sensíveis ao Contexto
  • Livres de Contexto
  • Linguagens Regulares
  • Nenhuma delas

Pregunta 4

Pregunta
Os ALL's não determinísticos são estritamente mais poderosos que os ALL's determinísticos?
Respuesta
  • Sim, jã foi provado
  • Não, não está provado
  • Ainda não foi provado

Pregunta 5

Pregunta
Data a linguagem a^(2n)bc^(n), com n maior ou igual a 1, se utilizarmos a cadeia de entrada $aaaabcc* , qual será o resultado?
Respuesta
  • Aceitação
  • Rejeição
  • Loop

Pregunta 6

Pregunta
Na vídeo aula 2 do site, no arco (q0, q1) ficou faltando o próximo movimento da unidade de controle. Assinale a alternativa que completa a máquina.
Respuesta
  • (q0, b) -> (q, y, L) E S
  • (q0, b) -> (q, y, R) E S
Mostrar resumen completo Ocultar resumen completo

Similar

Quiz de Máquinas de Turing Determinísticas
Loys Gibertoni
Senso Comum e Ciência
Thaís Pontes
Classificação da constituição
Als Treinamentos
Termômetro - 28/10/2015
Silas Júnior
LIDERANÇA
Luciane Eckert
Operações Fechadas sobre LR
eric.antunes.94
Quiz de Máquinas de Turing Determinísticas
Weverton Sullivan
Quiz de Máquinas de Turing Determinísticas
Rodrigo dos Santos Felix
Senso Comum e Ciência
ALINE BOANOVA
Quiz teste_1
douglasrndn