Lenguajes y Expresión Regular

¿Qué es lenguaje?

Un conjunto de cadenas, todas ellas seleccionadas de un Σ∗, donde Σ es un determinado alfabeto se denomina lenguaje. Si Σ es un alfabeto y L ⊆ Σ∗, entonces L es un lenguaje de Σ. Un lenguaje de Σ no necesita incluir cadenas con todos los símbolos de Σ, ya que una vez que hemos establecido que L es un lenguaje de Σ, también sabemos que es un lenguaje de cualquier alfabeto que sea un superconjunto de Σ.

EJEMPLO: Seria el inglés, donde la colección de las palabras correctas inglesas es un conjunto de cadenas del alfabeto que consta de todas las letras.

EJEMPLO: Es el lenguaje C, o cualquier otro lenguaje de programación, donde los programas correctos son un subconjunto de las posibles cadenas que pueden formarse a partir del alfabeto del lenguaje

¿Qué es una Expresión Regular?

Una expresión regular es una forma de representar los lenguajes regulares, y se construye utilizando caracteres del alfabeto sobre el cual se define el lenguaje.Por tanto, las expresiones regulares sirven como lenguaje de entrada de muchos sistemas que procesan cadenas. Algunos ejemplos son los siguientes:

EJEMPLO: Comandos de búsqueda tales como el comando grep de UNIX o comandos equivalentes para localizar cadenas en los exploradores web o en los sistemas de formateo de texto. Estos sistemas emplean una notación de tipo expresión regular para describir los patrones que el usuario desea localizar en un archivo. Los distintos sistemas de búsqueda convierten la expresión regular bien en un AFD o en un AFN y simulan dicho autómata sobre el archivo en que se va a realizar la búsqueda

EJEMPLO. Generadores de analizadores léxicos, como Lex o Flex. Recuerde que un analizador léxico es el componente de un compilador que divide el programa fuente en unidades lógicas o sintácticas formadas por uno o más caracteres que tienen un significado. Entre las unidades lógicas o sintácticas se incluyen las palabras clave (por ejemplo, while), identificadores (por ejemplo, cualquier letra seguida de cero o más letras y/o dígitos) y signos como + o <=. Un generador de analizadores léxicos acepta descripciones de las formas de las unidades lógicas, que son principalmente expresiones regulares, y produce un AFD que reconoce qué unidad lógica aparece a continuación en la entrada.

Autómatas que acepte par de "0"