Automatos Limitados Linearmente

Question 1 of 6

1

O que difere uma Máquina de Turing (MT) para um Autômato Linearmente Limitado (ALL)?

Select one of the following:

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

Explanation

Question 2 of 6

1

Quais são os possíveis resultados de uma linguagem ALL quando se testa uma cadeia de entrada?

Select one of the following:

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.

Explanation

Question 3 of 6

1

Os ALL's são máquinas reconhecedoras de quais tipos de linguagens?

Select one or more of the following:

Sensíveis ao Contexto
Livres de Contexto
Linguagens Regulares
Nenhuma delas

Explanation

Question 4 of 6

1

Os ALL's não determinísticos são estritamente mais poderosos que os ALL's determinísticos?

Select one of the following:

Sim, jã foi provado
Não, não está provado
Ainda não foi provado

Explanation

Question 5 of 6

1

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?

Select one of the following:

Aceitação
Rejeição
Loop

Explanation

Question 6 of 6

1

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.

Select one of the following:

(q0, b) -> (q, y, L) E S
(q0, b) -> (q, y, R) E S

	Created by GRUPO 11 about 9 years ago

Quiz de linguagens formais

Automatos Limitados Linearmente

Automatos Limitados Linearmente

Question 1 of 6

O que difere uma Máquina de Turing (MT) para um Autômato Linearmente Limitado (ALL)?

Select one of the following:

Explanation

Question 2 of 6

Quais são os possíveis resultados de uma linguagem ALL quando se testa uma cadeia de entrada?

Select one of the following:

Explanation

Question 3 of 6

Os ALL's são máquinas reconhecedoras de quais tipos de linguagens?

Select one or more of the following:

Explanation

Question 4 of 6

Os ALL's não determinísticos são estritamente mais poderosos que os ALL's determinísticos?

Select one of the following:

Explanation

Question 5 of 6

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?

Select one of the following:

Explanation

Question 6 of 6

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.

Select one of the following:

Explanation