O que difere uma Máquina de Turing (MT) para um Autômato Linearmente Limitado (ALL)?
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
Quais são os possíveis resultados de uma linguagem ALL quando se testa uma cadeia de entrada?
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.
Os ALL's são máquinas reconhecedoras de quais tipos de linguagens?
Sensíveis ao Contexto
Livres de Contexto
Linguagens Regulares
Nenhuma delas
Os ALL's não determinísticos são estritamente mais poderosos que os ALL's determinísticos?
Sim, jã foi provado
Não, não está provado
Ainda não foi provado
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?
Aceitação
Rejeição
Loop
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.
(q0, b) -> (q, y, L) E S
(q0, b) -> (q, y, R) E S
Bitte warte - es wird geladen…