A Função que comanda as leituras e gravações,
Por: kiviacelia • 24/10/2017 • Seminário • 1.368 Palavras (6 Páginas) • 224 Visualizações
- Recursividade à Esquerda
No desenvolvimento de algoritmos reconhecedores é desejável que a gramática que representa a linguagem não seja recursiva à esquerda.
Recursividade a esquerda ocorre quando uma variável deriva ela mesma de forma direta ou indireta, como o símbolo mais a esquerda de uma subpalavra gerada
.
[pic 2]
Eliminar a recursividade à esquerda é possível transformando a regra que possui a recursividade à esquerda em outras duas, como no exemplo abaixo.
[pic 3]
[pic 4]
Na gramática abaixo é possível observar duas regras que são recursivas à esquerda.
[pic 5]
Aplicando a transformação na primeira e na segunda regra:[pic 6][pic 7][pic 8][pic 9][pic 10][pic 11]
[pic 12] [pic 13][pic 14][pic 15][pic 16][pic 17][pic 18][pic 19][pic 20][pic 21][pic 22][pic 23][pic 24][pic 25][pic 26][pic 27][pic 28][pic 29][pic 30][pic 31][pic 32][pic 33][pic 34][pic 35][pic 36][pic 37][pic 38][pic 39][pic 40][pic 41][pic 42][pic 43]
A gramática equivalente sem recursividade à esquerda será:
[pic 44]
Realizando o mesmo procedimento na gramática abaixo, obteremos:
[pic 45]
- Máquina de Turing
Proposta em 1936 pelo Matemático Inglês Alan Turing, a maquina consiste basicamente em três partes:
Fita: Usado simultaneamente como dispositivo de entrada, saída e memória de trabalho;
Unidade de Controle: Reflete o estado corrente da máquina, possuindo uma unidade de leitura e gravação a qual acessa uma célula da fita de cada vez e movimenta-se para a esquerda ou direita;
Programa ou Função de Transição: Função que comanda as leituras e gravações, o sentido de movimento da cabeça e define o estado da máquina.
A fita é dividida em células, onde cada uma armazena um símbolo. Os símbolos podem pertencer ao alfabeto de entrada, ao alfabeto auxiliar, ser “branco” ou “marcador de inicio de fita”.
Inicialmente, a palavra a ser processada ocupa as células à esquerda após o marcador de inicio de fita, ficando as demais células com “branco”. A cabeça da fita lê o símbolo de uma célula de cada vez e grava um novo símbolo, após a leitura/gravação a cabeça move uma célula para a direita ou esquerda. Tanto o símbolo quanto o sentido do movimento são definidos pelo programa. O programa é uma função que, dependendo do estado corrente da máquina e do símbolo lido, determina o símbolo a ser gravado, o sentido do movimento da cabeça e o novo estado.
Uma maquina de Turing é uma 8-tupla
[pic 46]
Na seguinte ordem: Alfabeto de símbolos, conjunto de estados, programa ou função de transição, estado inicial, conjunto de estados finais, alfabeto auxiliar, símbolo especial branco, marcador de inicio de fita.
A função de transição será:
[pic 47]
Um estado que lê um símbolo, vai para outro estado e escreve um símbolo e define a direção.
Exemplo:
A máquina de Turing a seguir tem um alfabeto {¬, 1}, onde ¬ representa o símbolo branco. Ela espera uma série de 1's na fita, com o cabeçote inicialmente no 1 mais à esquerda, e duplica os 1's com um ¬ no meio. Por exemplo, "111" torna-se "111¬111". O conjunto dos estados é {s1, s2, s3, s4, s5} e o estado inicial é s1. A tabela de ação é dada a seguir.
Est. Símb. Símb. Est.
Act. Lido Escr. Mv. Novo
---- ----- ----- --- ----
s1 1 ¬ → s2
s2 1 1 → s2
s2 ¬ ¬ → s3
s3 ¬ 1 ← s4
s3 1 1 → s3
s4 1 1 ← s4
s4 ¬ ¬ ← s5
s5 1 1 ← s5
s5 ¬ 1 → s1
A primeira linha desta tabela pode ser lida como: "Se a máquina estiver no estado s1 e o símbolo lido pelo cabeçote for 1, então escreva o símbolo ¬, mova uma posição para a direita e mude o estado para s2".
Uma computação nesta máquina de Turing pode ser, por exemplo: (a posição do cabeçote é indicada mostrando-se a célula em negrito)
Passo Estado Fita
----- ------ -------
1 s1 11
2 s2 ¬1
3 s2 ¬1¬
4 s3 ¬1¬¬
5 s4 ¬1¬1
6 s5 ¬1¬1
7 s5 ¬1¬1
8 s1 11¬1
9 s2 1¬¬1
10 s3 1¬¬1
11 s3 1¬¬1¬
12 s4 1¬¬11
13 s4 1¬¬11
14 s5 1¬¬11
...