| |
| Acadêmico(a): Fernando Rafael Piccini |
| Título: Inclusão do Algoritmo de Transformação de um Autômato Finito em Expressão Regular no \'Editor de Autômatos Finitos\' |
| |
| Introdução: |
| A Teoria da Computação é fundamental para a Ciência da Computação. Não só proporciona um adequado embasamento teórico necessário para um correto e amplo entendimento da ciência envolvida na computação, como também propicia o desenvolvimento de um raciocínio lógico e formal, cada vez mais necessário em todas as subáreas da computação. Segundo Terada (2005), “pesquisas em Teoria da Computação têm produzido estruturas de dados eficientes e algoritmos que foram incorporados a muitas ferramentas de software e produtos de hardware”. De acordo com Menezes (1998, p. 4), a Teoria da Computação introduz conceitos fundamentais que são desenvolvidos em outras áreas como, por exemplo: biologia computacional (modelos para redes de neurônios), matemática (lógica), lingüística (gramáticas para linguagens naturais), entre outras. A Teoria da Computação também aborda o processamento de funções e o reconhecimento de linguagens (base de estudo de linguagens formais), bem como, trata da análise e do estudo da complexidade de algoritmos. Com isso pode-se expressar de forma abstrata a eficiência de um algoritmo, descrevendo o seu tempo de execução e calculando o tamanho do problema (quantidade de dados) (WANGENHEIM, 1997). Com o surgimento da Teoria da Computação, criou-se uma nova sub-área, a Teoria de Linguagens Formais, que originou-se na década de 1950 com o objetivo de desenvolver teorias relacionadas com as linguagens naturais. Foi verificado que essa teoria era extremamente importante para linguagens artificiais, em especial, para as linguagens de programação. Dessa forma, as linguagens formais assumem um importante papel na ciência da computação (MENEZES, 1998, p. 1). Dentro dessa teoria, encontra-se a teoria dos autômatos finitos que tem as mais diversas aplicações. Como exemplos podem ser citados: analisadores léxicos (parte integrante de compiladores); editores de textos; sistemas de pesquisa e atualização em arquivos (em geral, do tipo busca e substituição de informação); sistemas para verificação de circuitos digitais e protocolos de comunicação; entre outras aplicações (HOPCROFT; ULLMAN; MOTWANI, 2002, p. 2). Considerando o estudo dos autômatos, verifica-se que existe uma carência de ferramentas para auxílio do conteúdo lecionado nas disciplinas relacionadas ao assunto, quais sejam Linguagens Formais e Compiladores. Observa-se também que os alunos encontram dificuldades em entender o conceito de autômatos e até mesmo em não conseguir associar teoria e prática. Em conseqüência disto, foi desenvolvido o Editor de Autômatos Finitos (EAF) (MORASTONI, 2002) com a finalidade de apoiar o processo de ensino-aprendizagem das disciplinas mencionadas. Porém, essa ferramenta possui limitações, entre elas: não permite salvar um autômato finito (AF) especificado; não permite transformar um AF para uma expressão regular (ER); não mostra os estados que geram o não determinismo e também não converte um autômato finito não-determinístico em um autômato finito determinístico. Nesse sentido, é importante o aprimoramento desta ferramenta, acrescentando novas funcionalidades, entre as quais destaca-se a inclusão de um algoritmo descrito em Silva (2006), para transformação de autômato finito em uma expressão regular. As melhorias descritas visam adequar a ferramenta às necessidades dos acadêmicos em compreender melhor a teoria estudada. Observa-se também que a verificação da validação do algoritmo descrito em Silva (2006) também é proposta, visto que o mesmo ainda não foi validado através de uma implementação. |
| |
|
