Seja uma MT T dada pelas quíntuplas: 1. (0, 1, 1, 0, D) 2. (0, b, 1, 1, H) Considere que 0 é um estado inicial e 1 é um estado final e a configur...
Seja uma MT T dada pelas quíntuplas:
1. (0, 1, 1, 0, D)
2. (0, b, 1, 1, H)
Considere que 0 é um estado inicial e 1 é um estado final e a configuração inicial da fita igual a 111, com brancos antes e depois da cadeia 111 e n é o tamanho da cadeia, neste caso igual a 3. Qual a função que calcula essa MT?
2n
2n+1 - 1
2n+1
2n -1
2n +1
2n
2n+1 - 1
2n+1
2n -1
2n +1
1. (0, 1, 1, 0, D)
2. (0, b, 1, 1, H)
Considere que 0 é um estado inicial e 1 é um estado final e a configuração inicial da fita igual a 111, com brancos antes e depois da cadeia 111 e n é o tamanho da cadeia, neste caso igual a 3. Qual a função que calcula essa MT?
2n
2n+1 - 1
2n+1
2n -1
2n +1
2n
2n+1 - 1
2n+1
2n -1
2n +1
Essa pergunta também está no material:
💡 1 Resposta
Ed 
A função que calcula essa MT é 2n+1. Explicação: A MT T começa no estado inicial 0 e lê o primeiro símbolo da fita, que é 1. De acordo com a quíntupla (0, 1, 1, 0, D), a MT escreve 1 na fita, muda para o estado 1 e move a cabeça da fita para a direita. A MT lê o segundo símbolo da fita, que também é 1. De acordo com a quíntupla (1, 1, 1, 1, H), a MT escreve b na fita, permanece no estado 1 e para a execução. Portanto, a MT T escreve 1b1 na fita e para no estado final 1. A cadeia de entrada tem tamanho 3, então n = 3. Substituindo n na função 2n+1, temos 2(3)+1 = 7. Portanto, a resposta correta é 2n+1.
✏️ Responder
Para escrever sua resposta aqui, entre ou crie uma conta
Outros materiais
Compartilhar