Question

Considere a linguagem L1 sobre o alfabeto E = {a, b} definida como L1 = { a^n, b^m, a^n | n, m >= 1 } .

É possível verificar que esta linguagem é livre de contexto. Consequentemente esta linguagem pode ser reconhecida por um autô´mato com pilha. Como uma máquina de Turing é um autô´mato mais genérico, a linguagem também pode ser reconhecida por uma máquina de Turing.

Implemente uma máquina de Turing que reconheça a linguagem L1 definida no texto base.

Answer 1

Boa tarde! Eu achei esse exercício parecido, de todos que pesquisei esse é o mais próximo, espero que ajude.

Answer 2

Considere a linguagem L_1 sobre o alfabeto Σ={a,b} definida como  L_1={(a^n b^m a^n !n,m≥1)}

É possível verificar que esta linguagem é livre de contexto. Consequentemente esta linguagem pode ser reconhecida por um autômato com pilha. Como uma máquina de Turing é um autômato mais genérico, a linguagem também pode ser reconhecida por uma máquina de Turing. Implemente uma máquina de Turing que reconheça a linguagem L_1 definida no texto base: