Lenguajes y expresiones 

Lenguajes

Un conjunto de cadenas, todas ellas seleccionadas de un Σ∗, donde Σ es un determinado alfabeto se denomina lenguaje. La elección del término “lenguaje” puede parecer extraña. Sin embargo, los lenguajes habituales pueden interpretarse como conjuntos de cadenas. Un ejemplo sería 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. La única restricción importante sobre lo que puede ser un lenguaje es que todos los alfabetos son finitos.

Definición de lenguajes mediante descripciones de conjuntos

Es habitual describir un lenguaje utilizando una “descripción de conjuntos”:

{w | algo acerca de w}

Esta expresión se lee “el conjunto de palabras w tal que (lo que se dice acerca de w a la derecha de la barra vertical)”. Algunos ejemplos son:

{w | w consta de un número igual de ceros que de unos }.

{w | w es un entero binario que es primo }.

{w | w es un programa C sintácticamente correcto }

 ejemplo de un autómata que un par de ceros

 

Expresiones regular

Definen una notación estructural que permite describir los mismos patrones que se pueden representar mediante los autómatas finitos. Se emplean en muchos tipos comunes de software, incluyendo herramientas para la búsqueda de patrones, por ejemplo, en textos o en nombres de archivo.

Operadores de las expresiones regulares

Las expresiones regulares denotan lenguajes. Por ejemplo, la expresión regular 01∗ +10∗ define el lenguaje que consta de todas las cadenas que comienzan con un 0 seguido de cualquier número de 1s o que comienzan por un 1 seguido de cualquier número de 0s. No esperamos que el lector sepa ya cómo interpretar las expresiones regulares, por lo que por el momento tendrá que aceptar como un acto de fe nuestra afirmación acerca del lenguaje de esta expresión.