Lenguajes regulares

LENGUAJES REGULARES
ANALISIS DESDE LENGUAJE C++

FUNDAMENTOS DE CIENCIAS DE LA COMPUTACION

ANDRES VARGAS CORREA

PRESENTACION DEL LENGUAJE REGULAR

En matemáticas, lógica, y ciencias de la computación, un lenguaje formal es un lenguaje cuyos símbolos primitivos y reglas para unir esos símbolos están formalmente especificados. Al conjunto de los símbolos primitivos se le llama elalfabeto (o vocabulario) del lenguaje, y al conjunto de las reglas se lo llama la gramática formal (o sintaxis). A una cadena de símbolos formada de acuerdo a la gramática se la llama una fórmula bien formada (o palabra) del lenguaje. Estrictamente hablando, un lenguaje formal es idéntico al conjunto de todas sus fórmulas bien formadas. A diferencia de lo que ocurre con el alfabeto (que debe ser unconjunto finito) y con cada fórmula bien formada (que debe tener una longitud también finita), un lenguaje formal puede estar compuesto por un número infinito de fórmulas bien formadas.
Por ejemplo, un alfabeto podría ser el conjunto {a,b}, y una gramatica podría definir a las fórmulas bien formadas como aquellas que tienen el mismo número de símbolos a que b. Entonces, algunas fórmulas bien formadasdel lenguaje serían: ab, ba, abab, ababba, etc.; y el lenguaje formal sería el conjunto de todas esas fórmulas bien formadas.
Para algunos lenguajes formales existe una semántica formal que puede interpretar y dar significado a las fórmulas bien formadas del lenguaje. Sin embargo, una semántica formal no es condición necesaria para definir un lenguaje formal, y eso es una diferencia esencial conlos lenguajes naturales.
En algunos lenguajes formales, la palabra vacía (esto es, la cadena de símbolos de longitud cero) está permitida, notándose frecuentemente mediante , o .
Una expresión regular, a menudo llamada también patrón, es una expresión que describe un conjunto de cadenas sin enumerar sus elementos. Por ejemplo, el grupo formado por las cadenas Handel, Händel y Haendel sedescribe mediante el patrón "H(a|ä|ae)ndel". La mayoría de las formalizaciones proporcionan los siguientes constructores: una expresión regular es una forma de representar a los lenguajes regulares (finitos o infinitos) y se construye utilizando caracteres del alfabeto sobre el cual se define el lenguaje. Específicamente, las expresiones regulares se construyen utilizando los operadores unión,concatenación y clausura de Kleene. Además cada expresión regular tiene un autómata finito asociado.
Para la realización de un compilador que reconozca un lenguaje regular utilizando como lenguaje de programación C++, la mayoría de veces se utiliza una librería llamada Regex.h, la cual utiliza funciones para hacer el análisis de estas expresiones regulares.
Pero antes de comezar hablemos un pocohablemos de que es el lenguaje de programación C++.
C++ es un lenguaje de programación diseñado a mediados de los años 1980 por Bjarne Stroustrup. La intención de su creación fue el extender al exitoso lenguaje de programación C con mecanismos que permitan la manipulación de objetos. En ese sentido, desde el punto de vista de los lenguajes orientados a objetos, el C++ es un lenguaje híbrido.
El nombreC++ fue propuesto por Rick Mascitti en el año 1983, cuando el lenguaje fue utilizado por primera vez fuera de un laboratorio científico. Antes se había usado el nombre "C con clases". En C++, la expresión "C++" significa "incremento de C" y se refiere a que C++ es una extensión de C.

PROBLEMA

Describir e implementar un programa basado en lenguaje de programación C++ que efectue un análisissintáctico de expresiones regulares y describa si estas pertenecen o no a un lenguaje regular.

SOLUCION
Por medio de un lenguaje de programación realizaremos un compilador que permita realizar un análisis semántico de un lenguaje regular, el cual estará regido por un conjunto de reglas las cuales delimitan cada una de las expresiones según la necesidad de esta.

Ejem
Reglas
Simbolo...