Automatas

Unidad 2 Expresiones Regulares

Historia:

Los orígenes de las expresiones regulares se encuentran en la teoría de autómatas y teoría del lenguaje formal, los cuales son parte de la informática teórica. Estos campos de estudiar los modelos de computación (autómatas) y las maneras de describir y clasificar los lenguajes formales. En la década de 1950, el matemático Stephen Cole Kleene describió estos modelos mediante su notación matemática llamada conjuntos regulares.

El uso de expresiones regulares en los estándares de información estructurados para el documento y modelado de bases de datos se inició en la década de 1960 y se amplió en la década de 1980 cuando los estándares de la industria como ISO SGML (precursored por ANSI "GCA 101-1983") consolidada. El núcleo de la estructura del lenguaje de especificación normas consiste en expresiones regulares. Su uso es evidente en el DTD sintaxis grupo de elementos.

Definición:

• Las expresiones regulares son series de caracteres que forman un patrón, normalmente representativo de otro grupo de caracteres mayores, de tal forma que podemos comparar el patrón con otro conjunto de caracteres para ver las coincidencias.

Dado un alfabeto finito ∑, se define una expresión regular.

• Una expresión regular es un patrón específico que proporciona medios flexibles y concisos para "igualar" (especificar y reconocer) cadenas de texto, tales como caracteres especiales, palabras o patrones de caracteres.

En los lenguajes de programación estas siempre están disponibles, aunque su sintaxis es relativamente uniforme, cada lenguaje varía dependiendo del dialecto que sea usado.

Las expresiones regulares se utilizan para abreviar la descripción de conjuntos regulares.

Una expresión regular define un patrón; una palabra pertenece al lenguaje definido por esa expresión regular si y sólo si sigue el patrón.

Una expresión regular que represente un lenguaje debe cumplir dos condiciones:

– Correcta: todas las palabras representadas por la expresión regular deben ser parte del lenguaje.

– Completa: toda palabra del lenguaje debe ser representada por la expresión regular.

Concatenación indica orden de los símbolos, la cerradura de Kleene permite repeticiones y + indica selección.

Dos expresiones que representan al mismo conjunto son llamadas equivalentes.

...