3964609
Description
Quiz by Amanda Ruiz, updated more than 1 year ago
|
Created by Amanda Ruiz
over 8 years ago
|
|
Question 1
Question
Uma Máquina de Turing é capaz de representar quais tipos de Linguagem da Hierarquia de Chomsky?
Answer
-
Linguagem Regular
-
Linguagem Sensível ao Contexto
-
Linguagem Recursivamente Enumerável
-
Linguagem Livre de Contexto
Question 2
Question
Uma Máquina de Turing, segundo a definição apresentada nos nossos módulos teóricos, é representada por uma:
Answer
-
Quádrupla
-
Quíntupla
-
Sêxtupla
-
Sétupla
Question 3
Question
A sétupla só é corretamente representada quando contém os seguintes elementos:
Um conjunto (não vazio) de estados do seu AF: Q
Um símbolo branco (neutro): b
Um alfabeto de símbolos da fita: Γ, b ∈ Γ
Um alfabeto de símbolos de entrada: Σ, Γ∖{b } ⊇ Σ
Uma função de transições para os estados em Q, definida como δ: (Q∖F) ✕ Γ → Q ✕ Γ ✕ { E, D }.
Um estado inicial: q, Q ∋ q
Um conjunto de estados finais (de aceitação): F, Q ⊇ F
Answer
- True
- False
Question 4
Question
Uma Máquina de Turing Determínistica contém um cabeçote de [blank_start]leitura e escrita[blank_end] que pode se mover para [blank_start]esquerda e para direita[blank_end], [blank_start]uma fita infinita[blank_end], uma [blank_start]máquina de estados[blank_end] e um alfabeto.
Answer
-
leitura
-
escrita
-
leitura e escrita
-
seleção
-
esquerda e para direita
-
esquerda
-
direita
-
uma fita infinita
-
uma fita finita
-
uma fita ciclica
-
um disco
-
pilha
-
fila
-
controladora
-
máquina de estados
Question 5
Question
No diagrama ao lado, embora possua uma representação de transições diferentes da que vimos, ainda representa um diagrama da função de transição de uma MT. Observando-a, qual linguagem ele deve aceitar?
Answer
-
L = { 0^n 1^n | n >= 0 }
-
L = { 0^n 1^n | n >= 1 }
-
L = { 0^i 1^j | i >= 0 , j >= 0 }
-
L = { 0^i 1^j | i >= 1 , j >= 1 }
Question 6
Question
Suponho um diagrama da função de transição de uma MT tal que não apareça o estado de rejeição e as transições que levam a ele. Pode-se dizer que essas transições e este estado não fazem parte da máquina?
Answer
- True
- False
Question 7
Question
Assinale as informações corretas:
Answer
-
A máquina apenas para se a entrada é aceita.
-
A máquina pode parar a qualquer momento.
-
A máquina nem sempre para.
-
Uma máquina pode ter mais de um estado de aceitação.
Question 8
Question
Sobre uma MTD:
Answer
-
O alfabeto de entrada pode conter o símbolo 'branco'
-
O alfabeto de entrada está contido no alfabeto da fita.
-
O estado inicial pode ser o mesmo do final
-
O estado de rejeição pode ou não fazer parte da sétupla, dependendo de sua representação.
-
O indicativo de L/R (E/D) não é necessário na notação de transição.
Question 9
Question
Qual é a linguagem aceita pela máquina representada ao lado?
Answer
-
a^n b^n (a|c) (a|c)^n , sendo n >= 0
-
a^n b^n (a|c) (a|c)^n , sendo n > 0
-
a^n b^n (a|c)^2n , sendo n >= 0
-
a^n b^n (a|c)^2n , sendo n > 0
-
a^n b^n (a|c)^n , sendo n >= 0
-
a*b*(a|c)*
Want to create your own Quizzes for free with GoConqr? Learn more.