TrabalhosGratuitos.com - Trabalhos, Monografias, Artigos, Exames, Resumos de livros, Dissertações
Pesquisar

A Função que comanda as leituras e gravações,

Por:   •  24/10/2017  •  Seminário  •  1.368 Palavras (6 Páginas)  •  203 Visualizações

Página 1 de 6

  • 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

...

Baixar como (para membros premium)  txt (6.2 Kb)   pdf (367.9 Kb)   docx (513.7 Kb)  
Continuar por mais 5 páginas »
Disponível apenas no TrabalhosGratuitos.com