Programas recursivos de dominio finito

U N I V E R S I D A D E L U S Í A D A D E L I S B O A

F a c u ld ad e de C i ê nc i as d a Ec o n o mí a e d a Em p re s a

Mestrado em Ciências da Computação

Programas recursivos de domínio finito

Hercílio Rui Dinis Duarte

Lisboa

Maio 2012

U N I V E R S I D A D E L U S Í A D A D E L I S B O A

F a c u ld ad e de C i ê nc i as e d a Ec o no mí a d a Em p re s a

Mestrado em Ciências da Computação



Lisboa

Maio 2012

APRESENTAÇÃO



Após verificar estudos anteriores sobre automatos finitos deterministicos e não

deterministicos, surge a necessidade de se efectuar um estudo sobre programas de

dominio finito, embora o presente trabalho irá simplesmente especializar-se nos

recursivos.

Neste trabalho, iremos estudar sobre os programas recursivos de dominio finito

baseando-se em transdutores que permitem fazer um controle recursivo de estados

finitos, ou seja, transdutores pushdown.

Após verificar-se resultados e concluir suas vantagens, iremos então simplificar este

trabalho ao simplifica-lo num diagrama mais simples.

Palavras-chave: Transdutores de estados finitos, Recursividade, Pilhas, Transdutores

pushdown

PRESENTATION

Recursive finite-domain programs


After verifying previous studies on deterministic finite automata and non-deterministic,

there is a need to conduct a study on finite domain programs, although this work will

specialize in just recursive.

In this paper, we study about the domain of recursive programs based on finite

transducers that allow a recursive finite state control, ie, pushdown transducers.

After checking up the results and conclude its advantages, then we will simplify the job

simplifying it to a simple diagram.

Keywords: finite-state tranducers, Recursion, Stacks, Pushdown transducers

LISTA DE ILUSTRAÇÕES

Ilustração 1 – Representação do processamento de uma pilha ........................................... 16 Ilustração 2 – Representação das partes de um transdutor pushdown. (GUARARI Eiton, 1998) ......................................................................................................................... 18 Ilustração 3 – Representação da abordagem sintática da Web 1.0 e 2.0 (GUARARI Eiton, 1998) ......................................................................................................................... 21 Ilustração 4 – Diagrama de estados do transdutor pushdown (GUARARI Eiton, 1998) ........ 22

PROGRAMAS RECURSIVOS DE DOMÍNIO FINITO

Hercílio Rui Dinis Duarte 13

LISTA DE ABREVIATURAS, SIGLAS E ACRÓNIMOS

PLN - Processamento de Linguagens Naturais

AFD - Autómatos Finitos Deterministicos

AFND - Autómatos Finitos Não Deterministicos

LIFO - Last in First Out



SUMÁRIO

1. Introdução .................................................................................................... 15

2. Programas recursivos de domínio finito ....................................................... 16

2.1. Recursividade ........................................................................................ 16

2.1.1. Tipos de recursividade .................................................................... 17

2.1.2. Descrições resumidas sobre recursividade ..................................... 18

2.2. Estrutura de uma pilha ........................................................................... 18

2.3. Trasndutores baseados em pilhas (pushdown) ..................................... 19

2.3.1. Estrutura .......................................................................................... 20

Fita de entrada (Input tape) ....................................................... 20 2.3.1.1.

Cabeçalho de entrada (Input head) ........................................... 20 2.3.1.2.

Controlo do estado finito ........................................................... 21 2.3.1.3.

Cabeçalho de saída .................................................................. 21 2.3.1.4.

Fita de saída ............................................................................. 21 2.3.1.5.

Cabeçalho pushdown (escrita e leitura) .................................... 21 2.3.1.6.

Fita pushdown ........................................................................... 21 2.3.1.7.

2.3.2. Cálculo de uma relação pelo transdutor pushdown ......................... 21

2.3.3. Diagrama em grafo do transdutor pushdown .................................. 22

3. Conclusão .................................................................................................... 24



1. INTRODUÇÃO

A teoria da computação apresenta uma diversa e complexa relação de várias relações

capazes de simular qualquer realidade automática. Nesta viajem, entende-se a

essência do funcionamento dos sistemas, o que está por trás, quais as principais

barreiras entre a compreensão homem-máquina assim como a relação de

compreensão entre estes.

Tal como foi proposto, começou-se por estudar a compreensão e o processamento

das linguagens naturais (PLN). Agora a realidade tornou possivel o estudo de

formalismos que representam a comunicação nos dispositivos computacionais. O

presente trabalho vem aboradar aspectos relacionados a programas que dependem

de memórias finitas e que de maneira recursiva simplificam os cálculos.

Os transdutores são tidos como dispositivos que convertem um tipo de energía para

outro, é muito usado na electricidade. Mas para a nossa realidade o termo transdutor

será aplicado pelo facto deste ser um dispositivo em que antes de fornecer um

determinado resultado primeiro trata de aplicar antes suas propriedades previamente

programadas. Pois atravês de uma sequência de acções iremos verficar como estás

propriedades se desenvolvem.



2. PROGRAMAS RECURSIVOS DE DOMÍNIO FINITO

MOREIRA (1997) afirma que, os modelos de computação podem ser caracterizados

em termos do tipo de memória que possuem e como se tem acesso a ela.

Cada tarefa de computação finita pode ser realizada por um circuito combinacional.

Embora este conceito seja muito importante, mas não é tão prático. Não podemos

simplesmente projectar um circuito especialmente a cada tarefa computacional. Em

vez disso, é aconselhavel executar tarefas computacionais com máquinas que

funcionam com uma memória auxiliar para o controle do fluxo de dados. (SAVAGE

John, 1997)

Apartir do conceito acima, temos então as máquinas de memória finita e as máquinas

de memória finita com característica recursiva.

Podemos pensar que uma das formas de determinarmos a recursividade de um

programa de domínio finito é através da observação e descrição dos elementos

relacionados a memória. A memória deverá permitir um acesso recursivo de maneira

finita aos seus objectos pré-definidos.

Segundo SAVAGE (1997), os programas recursivos de domínio finito, funcionam tendo

em sua base a implementação de uma memória auxiliar Pushdown (uma pilha), isto é,

o armazenamento sobre esta é efectuado numa ordem LIFO (Last In, First Out).

2.1. RECURSIVIDADE

Segundo CRESPO (2001), A recursividade1 é a metodología de descrever uma

estrutura, em que um dos elementos é a descrição da própria estrutura.

A recursividade permite que possamos definir infinitos objectos de uma maneira

simples e objectiva. É uma técnica bastante poderosa para o desenvolvimento de

algoritimos.

Podemos verificar um comportamento recursivo na definição de uma função factorial:

1 Em outras palavras significa recorrência, enquanto uma data equação não é igualada a

definição de sua base.



1)!1.(

01!

nsenn

ensen

Segundo KOWALTOWSKI (2010), em algoritimia uma estrutura de dados recursivos

pode definir-se atravês dos seguintes procedimentos:

void Exemplo (T1 x1 , T2 x2 , . . . ) {

S1 y1; S2 y2; . . . ;

Ci ; /* Comandos i n i c i a i s */

i f (E ( . . . ) ) {

C0 ; /* Caso base */

} e l s e { /* Chamadas r e c u r s i v a s */

C1 ; Exemplo ( e11 , e12 , . . . ) ;

C2 ; Exemplo ( e21 , e22 , . . . ) ;

C3 ; Exemplo ( e31 , e32 , . . . ) ;

. . . ;

Cm; Exemplo ( em1 , em2 , . . . ) ;

Cf ;

}

}

2.1.1. TIPOS DE RECURSIVIDADE

De uma forma objectiva e lógica de enquadramento do conceito recursividade em

nosso projecto iremos nos basear em dois tipos. Tal como NETO, António (1998)

classifica como tipos de recursividade o seguinte:

Recursividade infinita



Um procedimento recursivo é infinito quando não existe nenhuma condição que faça o

procedimento ser interrompido.

Recursividade finita

A recursão finita é conhecida quando se encontra uma estrutura de condição de

paragem em algum momento da execução de um programa.

2.1.2. DESCRIÇÕES RESUMIDAS SOBRE RECURSIVIDADE

Num programa recursivo deve haver a garantia que o processo seja finito.

Caso contrario o programa estará a fazer infinitas chamadas recursivas. Neste

caso deve haver um estado de paragem.

O estado de paragem de um programa recursivo é determinado através de um

subprograma associado denominado como a base do processo.

A rotina recursiva trabalha sobre uma instância, e para cada chamada

recursiva deve haver garantia que a instância que será passada a ele seja

sempre mais restrita que a chamada superior.

Através de resumos acima, verificamos que a recursividade finita é aplicada em

sistemas da computação, de formas a e evitar que estes sistemas sejam

infinitamente recursivos.

2.2. ESTRUTURA DE UMA PILHA

Segundo LOPES (1999), Uma pilha que também é conhecida como stack, é um

sistema usado para o armazenamento de dados. O seu critério de acesso é definido

pelo facto do último elemento que entra na estrutura, ser o primeiro a sair.

LOPES (1999) também afirma que, as pilhas são utilizadas para guardar dados que

devem ser processados em ordem inversa de chegada e que são muito utilizadas em

sistemas operativos, compiladores e nas instruções de programas que realizam

chamadas de subprogramas (recursividade).

NETO, António (1998) apresenta como afirmação de que, uma pilha é de extrema importância para o entendimento de um processo recursivo.



Mediante as afirmações apresentadas, podemos supor que uma pilha é um sistema

conceptual que representa uma memória com a seguinte estrutura:

Operações básicas de uma pilha:

sobreposição de um novo elemento;

retirar o elemento do topo da pilha;

verificar qual é o elemento no topo da pilha;

verificar se a pilha está vazia.

Para este trabalho, iremos admitir a apresentação de uma memória recursiva baseada

em pilhas denominada como Transdutor pushdown e que iremos estudar no

subcapítulo seguinte.

2.3. TRASNDUTORES BASEADOS EM PILHAS (PUSHDOWN)

Para GURARI (1989), um trasndutor pushdown é uma máquina abstracta de controlo

de estados finito mas de forma recursiva.

Ilustração 1 – Representação do processamento de uma pilha



O Conceito de transdutores finito vem dar a possibilidade de esquematizar-mos um

programa que funciona mediante uma entrada, um estado e uma saida. O transdutor

não deixa de ser um automato, mas com a diferença deste ter em sua estrutura uma

memória que diretamente interage com a unidade de controlo.

Pelo facto contarem com uma memória antes de fornecer um determinado resultado é

que atribui a caracteristica de serem chamados de transdutores finitos que os

distingue dos demais tipos de automatos.

O termo recursividade nos transdutores de estados finitos é tido como verdade no

momento em que a pesquisa que a unidade de controle realiza a memória é do tipo

LIFO, ou seja, obdecendo uma estrutura de dados em pilha. Neste caso, o transdutor

deixa de ser simplesmente transdutor de controle finito e passa a ser transdutor de

controle finito recursivo (pushdown).

2.3.1. ESTRUTURA

FITA DE ENTRADA (INPUT TAPE) 2.3.1.1.

A fita de entrada permite apresentar a sequência determinada do conjunto de simbolos

do alfabeto a ser reconhecido.

CABEÇALHO DE ENTRADA (INPUT HEAD) 2.3.1.2.

O Cabeçalho trata de efectuar a leitura a apartir da fita dos dados de entrada e deixar

os dados disponíveis para serem controlados finitamente.

Ilustração 2 – Representação das partes de um transdutor pushdown. (GUARARI

Eiton, 1998)



CONTROLO DO ESTADO FINITO 2.3.1.3.

Também tratado como unidade de controlo finito, é a parte principal que permite ter

controle da sequência de cálculos e trata de conectar-se a memória auxiliar de

maneira a obter um maior desempenho. Em que no caso, a memória é uma pilha.

CABEÇALHO DE SAÍDA 2.3.1.4.

O cabeçalho que permite simplesmente escrever o reasultado final, como diz o próprio

termo, é apenas de saida, de modos a que a informação após ter passado por uma

regra rigorosa é então apresentada.

FITA DE SAÍDA 2.3.1.5.

Esta fita, é entidade que exibe os dados atravês de uma escrita depois do cabeçalho

de saida efectuar o seu trabalho.

CABEÇALHO PUSHDOWN (ESCRITA E LEITURA) 2.3.1.6.

O Cabeçalho de pushdown responsabiliza-se de efectuar continuamente uma

pesquisa sobre a mémoria (fita pushdown) em busca dos dados previamente

ordenados.

FITA PUSHDOWN 2.3.1.7.

É vista como sendo a memória auxiliar do sistema. tal como foi estudado, esta ordena

os dados obedecendo as regras seguindo o principio de uma pilha.

2.3.2. CÁLCULO DE UMA RELAÇÃO PELO TRANSDUTOR PUSHDOWN

A imagem a baixo proposta por GUARARI (1998), representa os diferentes estados de

um transdutor no reconhecimento da linguagem { (aibi, ci) | i >1 }, sendo que no

primeiro estado o transdutor assume em sua fita pushdown (a chamada memória

auxiliar LIFO), o simbolo Z0 que marca o fundo da pilha. O cálculo começa pela leitura

da sequência de a´s pela fita de entrada, e enquanto ocorre essa leitura é dado

também como entrada de forma sequencila desses valores na memória pushdown, os

simbolos são lidas um a um a partir da entrada, ou seja, de forma léxica.



Assim que M termina a leitura dos a’s, começa a leitura dos b´s, e na ocorrência dessa

leitura é recuperado um a para cada b lido e ao mesmo tempo é escrito um c na fita de

saida.

A linguagem será aceite caso na leitura do último b, haver a recuperação do último a

(permitindo assim uma deslocação para o valor inicial da memória, Z0) e a escrita do

último c. Caso contrário, ou seja, se o último b for lido e não haver a recuperação de

Z0, a linguagem não será reconhecida.

2.3.3. DIAGRAMA EM GRAFO DO TRANSDUTOR PUSHDOWN

Segundo Guarari (1998), graficamente um transdutor Pushdown é representado

obdecendo o seguinte:

M = <Q, Ʃ, Γ, Δ, δ, q0, Z0, F>, sendo que:

Q – Conjunto de estados Ʃ - Alfabeto Γ – Alfabeto pushdown

Δ – Alfabeto de saida

Ilustração 3 – Representação da abordagem sintática da Web 1.0 e 2.0 (GUARARI Eiton, 1998)



δ – Tabela das regras de transição

q0 – Estado inicial

Z0 - Simbolo do fundo da pilha

F – Estado final

Regras de transição

O conjunto das regras de transições (q, α, β, p, ϓ, ρ) são representados com p e q

que são o conjunto de estados em Q, α é tanto um simbolo de entrada ou uma string

vazia, β é tanto um simbolo pushdown ou uma string vazia, é uma string dos simbolos

pushdown, e ρ é tanto um simbolo de saida ou uma string vazia.

O automato resume-se como inicio a leitura de a´s e b´s no estado inicial, transitando

(escrevendo) o valor de c para o estado q1, e no final transita o ultimo valor que por

característica é o Z0 acompanhado das strings que o representam.

Ilustração 4 – Diagrama de estados do transdutor pushdown (GUARARI Eiton, 1998)



3. CONCLUSÃO

A ordem como abordei este tema, permitiu exibir de forma sintética a relação de um

programa, sua memória e propriedades recursivas. E facilmente os conceitos retirados

podem ser integrados em projectos anteriores ou ainda por surgir no ambito da

disciplina da Teoria da computação. Tratou-se de uma abordagem geral que

facilmente poderá insentivar o leitor a continuar suas pesquisas atravês da forma livre

como poderá interpretar e tirar suas conclusões por tratar-se de um trabalho

tipicamente acadêmico.

O essencial neste tema foi demonstrar uma daquelas coisas que existem e que são

eternas no ramo da computação. Por mais que surjam sistemas sofisticados de

computação, estes encaixarão sempre nestes modelos formais.



REFERÊNCIAS

SAVAGE, John (1997) – Models of computation – Exploring the power of computing

[Em linha]. [Consult. 06 Mai. 2012]. DisponíveI em WWW:

<http://www.cs.brown.edu/people/jes/book>.

MOREIRA, Nelma (1996) – Computabilidade – Uma Introdução [Em linha]. [Consult.

06.Mai.2012].Disponível: WWW:<http://www.dcc.fc.up.pt/~nam/publica/compdec.pdf>.

CRESPO, Rui (2001) – Processadores de linguagens – Da Concepção à

implementação. 2ª ed. Lisboa: IST Press.

KOWALTOWSKI, Tomasz (2010) – Estrutura de dados e técnicas de programação

[Em linha]. [Consult. 06 Mai. 2012]. Disponível em

WWW:<http://colibri.ic.unicamp.br/~tomasz/cursos/mc202/transp_ho_acum.pdf>.

LOPES, Arthur (1999) – Estrutura de dados – Para a construção de softwares. 1ª Ed.

Canoas: Editora da Ulbra.

NETO, António (1998) – Explorando recursão e fractals [Em linha]. [Consult. 06 Mai.

2012].Disponível:WWW:<http://lsm.dei.uc.pt/ribie/docfiles/txt200342415342159M.PDF

>.

GUARI, Eiton (1989) – Introduction to theory of the computation. [Em linha].

[Consult.06.Mai.2012].Disponível:WWW:<http://www.cse.ohio-

state.edu/~gurari/theory-bk/theory-bk.html>.

ANEXOS



LISTA DE ANEXOS

Anexo A - Transdutor de controle finito

Anexo B - Uma máquina de estados finito



ANEXO A Transdutor de controle finito





ANEXO B Uma máquina de estados finitos



Documents

Programas recursivos de dominio finito