Mis trabajos

Autómatas y Lenguajes - Año 2007
´ Teor´a 3: Expresiones Regulares - Gramaticas Regulares ı Propiedades de los LR

´ Departamento de Informatica ´ Facultad de Cs. Fco. Matematicas y Naturales

Universidad Nacional de San Luis San Luis - Argentina

´ ˜ Automatas y Lenguajes - Ano 2007– p.1/35

Expresiones Regulares (ER)
Otras alternativas para denotar lenguajes regulares. Las expresionesregulares son otro tipo de notación para denotar lenguajes regularse, por lo tanto definen exactamente los mismos lenguajes que las distintas fomas de autómatas que hemos visto (AFD, AFND, AFND-ǫ). No obstante ofrecen algunas cosas que los autómatas no, una forma declarativa de expresar las cadenas que queremos aceptar. Por lo tanto, las ER sirven como lenguaje de entrada para muchos sistemas queprocesan cadenas: 1. Comandos de búsqueda tales como el grep de UNIX. 2. Generadores de analizadores lexicográficos, tales como Lex o Flex.

´ ˜ Automatas y Lenguajes - Ano 2007– p.2/35

Operadores Antes de describir la notación de las ER necesitamos enumerar las tres operaciones sobre lenguajes que los operadores de las ER representan: 1. La unión de dos lenguajes L y M , denotado por L ∪ M ,es el conjunto de todas las cadenas que están en L o en M , o en ambos. 2. La concatenación de lenguajes L y M es el conjunto de cadenas que pueden ser formadas tomando cualquier cadena de L y concatenándole cualquier cadena de M . 3. La clausura o clausura reflexo-transitiva de un lenguaje L, denotada L∗ , representa el conjunto de cadenas que pueden ser formadas tomando cualquier número decadenas de L, con repeticiones, concatenándolos a todos ellos. Recordar que: ∅∗ = {λ} ∅0 = {λ} ∅i = ∅, ∀i ≥ 1

´ ˜ Automatas y Lenguajes - Ano 2007– p.3/35

Como construir ER
Una ER sobre algún alfabeto Σ se define recursivamente de la siguiente manera: Base: 1. ∅ es una ER, que denota el lenguaje ∅. 2. λ es una ER, que denota el lenguaje {λ}. 3. a ∈ Σ es una ER, que denota el lenguaje {a}.Inducción: 1. Si E y F son ER, luego E.F es una ER, que denota la concatenación de L(E) y L(F ). 2. Si E y F son ER, luego E + F es una ER, que denota la unión de L(E) y L(F ). 3. Si E es una ER, luego E ∗ es una ER, que denota la clausura de L(E). 4. Si E es una ER, luego (E) es una ER, que denota el mismo lenguaje que E.

´ ˜ Automatas y Lenguajes - Ano 2007– p.4/35

La precedencia de losoperadores es de mayor a menor: *, ., +. La asociatividad es de izquierda a derecha. La definición de como construir ER dada anteriormente, solo refleja la forma correcta de construir una ER, pero necesitamos determinar lo que cada una denota.
´ Definicion.

La función Φ : LER → 2Σ , es denominada la función de valuación. LER es el conjunto de

∗

todas las posibles expresiones regulares. Φ toma comoargumento una ER bien formada (según definición anterior) y da como resultado el conjunto de cadenas denotado por dicha ER.

´ ˜ Automatas y Lenguajes - Ano 2007– p.5/35

Luego, 1. Φ(∅) = {}, el conjunto vacío. 2. Φ(λ) = {λ}, el conjunto formado por la cadena de longitud nula. 3. Φ(a) = {a}. 4. Φ(E.F ) = Φ(E).Φ(F ), concatenación de conjuntos. 5. Φ(E + F ) = Φ(E) ∪ Φ(F ). 6. Φ(E ∗ ) = Φ∗ (E),clausura. 7. Φ((E)) = Φ(E).

´ ˜ Automatas y Lenguajes - Ano 2007– p.6/35

Ejemplo Dar una ER que denote el lenguaje consistente de: al menos dos ceros precedidos por cualquier número de 0’s seguidos por cualquier número de 1’s. Primero podemos desarrollar una ER para 0 y para 0 que denotan los lenguajes {0} y {0} respectivamente. Si concatenamos las dos expresiones 00, obtenemos el lenguaje{00}. Veamos ahora como construir el resto, cualquier número de 0’s lo podemos escribir como 0∗ y lo mismo para cualquier número de 1’s, 1∗ y ahora debemos describir la concatenación 0∗ 1∗ . La expresión regular completa es: 0∗ 1∗ 00

´ ˜ Automatas y Lenguajes - Ano 2007– p.7/35

Autómatas Finitos y Expresiones Regulares
Para mostrar que las ER definen la misma clase de lenguajes que los AF,...