| |
| Acadêmico(a): Josiane Patrícia Morastoni |
| Título: Editor de Autômatos Finitos |
| |
| Introdução: |
| Na década de 1950 originou-se a Teoria das Linguagens Formais com o objetivo de desenvolver teorias relacionadas com as linguagens naturais. Foi verificado que esta teoria era importante para o estudo de linguagens artificiais e, em especial, para as linguagens originárias na Ciência da Computação, mais especificamente as linguagens de programação. Uma linguagem de programação é uma das ferramentas usadas para o desenvolvimento de determinada aplicação. A escolha da mesma deve ser feita objetivando a construção de programas legíveis, confiáveis e com baixo custo de compilação. Estudar os conceitos de linguagens, conforme Sebesta (2000), visa permitir que: a) o acadêmico aumente sua capacidade de expressar idéias visto que, conhecendo mais recursos e linguagens, adquire aos poucos experiência para estruturar e desenvolver melhor um programa; b) o acadêmico adquira maior conhecimento para escolher a linguagem mais apropriada a um domínio de problemas; c) o acadêmico tenha maior facilidade no aprendizado de novas linguagens; d) o acadêmico entenda melhor a importância da implementação; e) o acadêmico possa projetar novas linguagens ou estender linguagens existentes, implementando compiladores eficientes. As disciplinas na área de compiladores são, de uma forma geral, o ponto de partida para o entendimento das linguagens de programação. No currículo do curso de Ciências da Computação da FURB, há disciplinas como Teoria da Computação, Linguagens Formais e Compiladores, onde são estudados os conceitos e as ferramentas da Teoria da Computação que podem ser usados para especificar linguagens de programação e construir compiladores. Um compilador é composto por vários módulos, sendo o primeiro o analisador léxico. Na implementação do analisador léxico são utilizados autômatos finitos, ou seja, reconhecedores de linguagens. Conforme Aho (1995), um reconhecedor para uma linguagem é um programa que toma como entrada uma seqüência x de símbolos e responde sim, se x for uma palavra da linguagem e não, em caso contrário. No caso de autômatos finitos, o reconhecimento é feito por uma máquina de estados capaz de observar apenas um símbolo de cada vez. A palavra finito é incluída no nome para ressaltar que um autômato só pode conter uma quantidade limitada de informações a qualquer momento. Tais informações são representadas por um conjunto finito de estados e de transições entre esses. Um autômato finito pode ser representado diagramaticamente por um grafo dirigido e rotulado, chamado de diagrama de transições, no qual os nós são os estados e os lados rotulados com os símbolos do alfabeto de entrada, determinam o próximo estado em função do estado atual e do símbolo de entrada. Há um estado inicial, chamado de estado de partida, e um ou mais estados, denominados estados finais, que indicam onde o autômato deve parar no processo de reconhecimento para que uma seqüência de símbolos de entrada seja aceita. Essa diagramação pode ser usada para representar tanto autômatos finitos não-determinísticos (AFND) quanto autômatos finitos determinísticos (AFD). Em um AFND mais de uma transição de estado pode ser possível para o mesmo símbolo de entrada a partir de um único estado. Já em um AFD existe no máximo uma transição de estado definida para cada símbolo a partir de um único estado. Os dois são capazes de reconhecer precisamente linguagens simples classificadas como regulares, mas existem diferenças. Por exemplo, os autômatos finitos determinísticos podem especificar reconhecedores mais rápidos do que os não-determinísticos. No entanto, podem possuir mais estados e transições, sendo mais complexos do que autômatos finitos não-determinísticos equivalentes. Autômatos finitos são os mais simples reconhecedores de linguagens. No entanto, durante estes anos cursando Ciências da Computação, constatou-se que os acadêmicos apresentam dificuldade no aprendizado dessa teoria. Assim, este trabalho apresenta o desenvolvimento de um Editor de Autômatos Finitos em função de não existir uma ferramenta adequada que auxilie a prática do conteúdo lecionado sobre esse assunto nas disciplinas de Linguagens Formais e de Compiladores. Com a ferramenta proposta, os acadêmicos serão capazes de construir e testar autômatos finitos determinísticos e não-determinísticos, possibilitando a validação dos mesmos. O desenvolvimento de uma ferramenta desse tipo visa não só motivar a compreensão dos conceitos envolvidos, como permitir que os acadêmicos possam relacionar teoria e prática. |
| |
|
