Linguagens formais

LFA - 4ª Lista Exercícios - Linguagens Sensíveis ao Contexto, Linguagens
Recursivamente Enumeráveis e Máquinas de Turing

1. Seja T a máquina de Turing T = ({q0, q1, q2, q3}, {a, [, ], #}, q0, {q3}, δ), onde δ é dado por: δ( q0, a) = ( q0, a, R) δ( q0, #) = ( q0, #, R) δ( q0, [ ) = ( q1, #, R) δ( q1, [ ) = ( q1, [ , R) δ( q1, #) = ( q1, #, R) δ( q1, ] ) = ( q2, #, L) δ( q2, x) = ( q2, x, L) para todo x ( a δ( q2, a) = ( q0, a, R) δ( q0, B) = ( q3, #, R)

É possível encontrar uma gramática para tal linguagem?

Resp:
Quíntuplas pertencentes à máquina T = ({q0, q1, q2, q3}, {a, [, ], #}, q0, {q3}, δ):
Q = {q0, q1, q2, q3},
Σ’ = {a, [, ], #}
S = q0 qa = q3 δ é dado do exercício

Movimentos da máquina:
|( q0 a q0 a R) |Movimentos |
|( q0 # q0 # R) |δ( q2, x) = ( q2, x, L) para todo x ( a |
|( q0 [ q1 # R) | |
|( q1 [ q1 [ R) |( q2 # q2 # L) |
|( q1 # q1 # R) |( q2 ] q2 ] L) |
|( q1 ] q2 # L) |( q2 [ q2 [ L) |
|( q2 a q0 a R) | |
|( q0 B qa # R) | |

Gramática:
S → BS | SB | &A
A → aA | Aa | #A | A# | [ A | A [ | ] A | A ] | BA | AB | qa

(regras baseadas em movimentos para a direita) a q0 → q0 a
# q0 → q0 #
# q1 → q0 [ [ q1 →