Turing Machine Quiz

1

Uma Máquina de Turing é capaz de representar quais tipos de Linguagem da Hierarquia de Chomsky?

1

Uma Máquina de Turing, segundo a definição apresentada nos nossos módulos teóricos, é representada por uma:

1

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

1

Uma Máquina de Turing Determínistica contém um cabeçote de ( leitura, escrita, leitura e escrita, seleção ) que pode se mover para ( esquerda e para direita, esquerda, direita ), ( uma fita infinita, uma fita finita, uma fita ciclica, um disco ), uma ( pilha, fila, controladora, máquina de estados ) e um alfabeto.

1

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?

1

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?

1

Assinale as informações corretas:

1

Sobre uma MTD:

1

Qual é a linguagem aceita pela máquina representada ao lado?

Questionário sorbe Máquina de Turing para disciplina Teoria da Computação e Linguagens Formais (ICMC-USP), turma B 2015

Turing Machine Quiz

Uma Máquina de Turing é capaz de representar quais tipos de Linguagem da Hierarquia de Chomsky?

Uma Máquina de Turing, segundo a definição apresentada nos nossos módulos teóricos, é representada por uma:

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?

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?

Assinale as informações corretas:

Sobre uma MTD:

Qual é a linguagem aceita pela máquina representada ao lado?