La transformación de lenguajes formales a autómatas finitos

Abstract

RESUMEN: Un lenguaje formal se puede definir por el conjunto de palabras, y para saber si una palabra pertenece a un lenguaje, se pueden utilizar autómatas diseñados a partir de la definición del lenguaje. Una clase de lenguajes muy importantes son los aceptados por autómatas finitos, también conocidos como lenguajes regulares. Un lenguaje regular arbitrario puede ser aceptado por diferentes autómatas finitos; por ello es interesante buscar aquellos que tengan buenas propiedades, para hacer el proceso lo más sencillo posible. Existe un algoritmo que, dada la descripción del lenguaje mediante una expresión regular, genera un autómata finito. Pero, en ciertas implementaciones, la transformación de una expresión regular en un autómata finito puede tardar más en ejecutarse que otra, aunque proporcionen los mismos resultados. En este documento nuestro objetivo es diseñar un conjunto de reglas que permitan transformar una expresión regular «problemática» en otra con mejores propiedades, pero manteniendo el mismo resultado de la expresión original. Nos apoyaremos en autómatas finitos para demostrar por qué hay un ahorro de tiempo de cómputo en una expresión y no en la otra, aun obteniendo los mismos resultados.

ABSTRACT: A formal language can be defined by the set of words. To solve the problem wether a word belongs to certain classes of languages, automata based on the language definition can be built. An important class of languages is the languages that can be defined as the words accepted by finite automata, also known as regular languages. Any regular language can be defined by a regular expresión. A particular regular language can be accepted by different finite automata; so it is interesting to find those with good properties, to make the computation as efficient as possible. There are algorithms that, given a regular expression, can generate a finite automaton. But, in some implementations, a regular expression can be more complex for computing than another, even though they define the same language. In this document our objective is to design a set of rules that allow as to transform a «problematic» regular expression into another one with better properties, while keeping the results of the original one. We will use finite automata to discuss why a regular expression need less time than another to achieve the same goal.