2020
Linguagens Formais e Autônomas.
Atividade Discursiva:
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.
> Minha Resposta:
Fórmula de Base:
Σ= {a, b}.
L1 = {an, bm, an | n, m ≥ 1}.
Tupla:
MT= { Q = {q0,q1,q2,q3,q4,q5,q6},
E = {a, b}, Γ = {a, b, x, w, β},
Q0 , β (Nulo ou vazio), {q6}, δ}.
Funções de Transição:
δ (q0, a) = (q1, x, D)
δ (q1, a) = (q2, x, D)
δ (q2, b) = (q3, w, D)
δ (q3, b) = (q4, b, E)
δ (q2, w) = (q3, w, D)
δ (q3, b) = (q4, w, D)
δ (q4, a) = (q5, x, D)
δ (q5, a) = (q4, a, E)
δ (q4, w) = (q5, x, D)
δ (q5, a) = (q6, x, D)
δ (q6, β) = (β, β, D).
Sendo L1 = aabbaa, que resulta em:
{q0abbaa | Xq1bbaa | XXq2baa | XXWq3aa | XXq2baa | XXWq3aa | XXWWq4a | XXWWXq5 | XXWWq4a | XXWWXq5 | XXWWXXq6 | XXWWXXβ.}
Soluções para a tarefa
Links para o estudo:
https://youtu.be/zqUU-fXdfos
https://youtu.be/4Hfd05u0MK0
https://youtu.be/DzD4_RobRbI
EXPLICAÇÃO
Passo a passo:
1- A linguagem L1 = { a^n, b^m, a^n | n, m >= 1 } diz que as letras: "a e b" estão sendo elevadas por "n,m" e que ambas podem receber um número maior ou igual a 1. Agora que entendeu, se eu atribuir um número>=1 como: 2, a palavra seria:
Exemplo: aabbaa
2- Agora vamos definir os outros elementos: (Q , E , Γ ,Q0, b(estado vazio, beta) , Qf , δ ). Começando pelo Q, pegamos o exemplo passado e contamos a casa como se fosse um vetor, assim:
a a b b a a vazio
q0 q1 q2 q3 q4 q5 q6
Definimos o vazio para a máquina finalizar.
3- Após isso definimos os outros elementos como:
Q0= estado inicial, no caso acima é o primeiro "a"
Qf= estado final que é o "Q6"
b=o conjunto vazio no 2 passo
Γ( conjunto dos alfabetos)= (a,b, X,Y e b)
Para que serve o X e Y?
X e Y entram como reconhecedores, eles vão ser colocados no lugar das letras ou simbolos reconhecidos e o beta vai ser colocado no final mostrando a finalização da máquina de turing. As transições entram aqui.
As transições informam a direção da máquina de turing.
Exemplo de transição:
(q0,a) = (q1,X,D)
Como se ler:
(estado atual, o que estou lendo nesse estado) = (próximo estado, escrevo o simbolo informando que reconheci a letra do estado atual, movimento da máquina: direita ou esquerda)
Continuando exemplo: (q0,a) = (q1,X,D)
a a b b a a vazio
q0 q1 q2 q3 q4 q5 q6
Próximo: (q1,a) = (q2,X,D)
X a b b a a vazio
q0 q1 q2 q3 q4 q5 q6
Próximo: (q3, b) = (q3,Y,D)
X X b b a a vazio
q0 q1 q2 q3 q4 q5 q6
Próximo: (q3, b) = (2,b,E)
X X Y b a a vazio
q0 q1 q2 q3 q4 q5 q6
... segue até o final
Nós definimos até agora o (Q, E, Γ, Q0, b, Qf e δ)
Agora você pode fazer sua máquina de estados se baseando no de cima, seguindo direto apenas para direita ou indo, voltando e indo novamente até o final.
