Lenguajes y Expresiones Regulares

Ahora vamos a centrar nuetra atención a lo que llamaremos una expresión regular, esta sirve como una descripcion algebraica de un lenguaje, de un lenguaje regular, la gran ventaja de trabajar con expresiones regurales en vez de con automatas que es las primeras te permiten ver visulamente (o de forma declarativa) las cadenas que vamos a aceptar.



Operaciones

Antes de nada veamos las operaciones en las expresiones regulares:

Unión:

Captura de pantalla 2017-03-31 a las 11.45.47 a.m..png

Veamos un ejemplo:

Captura de pantalla 2017-03-31 a las 11.51.20 a.m.

Concatenación:

La concatenación es el conjunto de todos las cadenas que se crean de concatenar cualquiera de las cadenas de los dos lenguajes.

Captura de pantalla 2017-03-31 a las 11.56.24 a.m.

Veremos un ejemplo:

Captura de pantalla 2017-03-31 a las 11.56.16 a.m.

Recuerda que epsilon es la “identidad” de las concatenaciones, es decir, que calculo la cadena concatenada con epsilon es la misma cadena.

Cerradura de Kleene:

Captura de pantalla 2017-03-31 a las 12.29.39 p.m..png

La cerradura es una operacion muy importante, esta te devuelve todos los strigns que pueden ser formados con al hacer la concatenacion de cualquier cantidad de strings de L.
Veamos un ejemplo, así podemos sacar las primeras iteraciones:

Captura de pantalla 2017-03-31 a las 12.29.25 p.m..png

Formas de una RE

Tenemos que saber que no solo hay una forma de expresar las expresiones regulares, por ejemplo, veamos como hacer una RE que sea capaz de recibir cadenas alternantes de 1 y 0.

L = { ε, 0, 1, 101, 10101, 1010101 … 01, 010, 01010 …}

Captura de pantalla 2017-03-31 a las 12.52.39 p.m.

Forma A

Captura de pantalla 2017-03-31 a las 12.52.50 p.m.

Forma B

Ejemplos:

(0 + 10*) L = { 0, 1, 10, 100, 1000, 10000, … }
(0*10*) L = {1, 01, 10, 010, 0010, …}
(0 + ε)(1 + ε) L = {ε, 0, 1, 01}
(a+b)*  L = { ε, a, b, aa , ab , bb , ba, aaa, …}
(a+b)*abb  L = {abb, aabb, babb, aaabb, abad, …}

Propiedades

Captura de pantalla 2017-03-31 a las 1.22.09 p.m.

Básica

Captura de pantalla 2017-03-31 a las 1.22.34 p.m.

No tan básicas

Captura de pantalla 2017-03-31 a las 1.22.26 p.m.

Las más Hardcore

 


De Expresiones Regulares a Autómatas

 

Para lograr esto vamos a ver varias “ε-NFA” base que nos sirve para encontrar RE más complejas:

  • Si el ε-NFA describe un RE: a

automata4

  • Si el ε-NFA describe un RE: Ø

Es deir, es imposible que exista tal RE.

automata5

 

  • Si el ε-NFA describe un RE: ε

Es decir, acepta cualquier RE.

automata6

  • Si el ε-NFA describe un RE: RS

Es decir, acepta cualquier RE que sea la concatenación de R seguido de S.

automata2.png

  • Si el ε-NFA describe un RE: R*

Es decir, acepta cualquier RE que sea la cerradura de R*.

automata1

  • Si el ε-NFA describe un RE: R+S

Es decir, acepta cualquier RE que bien R o S.

automata3

 

Ejemplo:

Usando esto, como piezas de LEGO, podemos hacer cualquiera RE, veamos todo esto con un ejemplo:

Captura de pantalla 2017-04-15 a las 4.30.53 p.m.

 

  • Primer Paso: Hacer un RE que exprese 0 + 1

Captura de pantalla 2017-04-15 a las 4.31.11 p.m.

  • Segundo Paso: Hacer un RE que exprese (0 + 1)*

Captura de pantalla 2017-04-15 a las 4.31.20 p.m.

  • Tercer Paso: Hacer un RE que exprese (0 + 1)*1(0 + 1)

Captura de pantalla 2017-04-15 a las 4.31.38 p.m.

 

 

 


De Automata a Expresión Regular

Los K-Caminos

No haré la explicación pero basado en estos diagramas podemos llegar a :

Captura de pantalla 2017-03-31 a las 1.48.03 p.m.

Captura de pantalla 2017-03-31 a las 1.48.10 p.m.

Recuerda que K no puede ser mas grande que la cantidad de estados:

Captura de pantalla 2017-03-31 a las 1.54.28 p.m.

Formula más pro

Espera, espera, ¿Que significa esta “fórmula”?

Para encontrar el Universo de las RE que acepta nuestro autómata tenemos que encontrar los K-Caminos…. Si, esto se explica mejor con un ejemplo…

Encontrar la RE de nuestro DFA (Ejemplo):

Captura de pantalla 2017-03-31 a las 2.11.27 p.m.

Nuestro Ejemplo

Nunca olvides que cuando i=j tenemos que añadir el epsilon.

Ahora si, los K-Caminos:

El pase de diapositivas requiere JavaScript.

La Solución

La expresión regular de un autómata es la union de todos los k-caminos en lo que i sea el estado inicial, j es el estado final.

Así en nuestro caso solo importa RE = (1∗0)(0 + 1)∗

 

 

 

 

 


Pumping Lemma

Este teorema es tan conocido que ni siquiera quise traducirlo, es demasiado famoso, total, veamos para que sirve el que s considerado el teorema mas importante de las expresiones regulares:

El Pumping Lemma sirve para probar que un lenguaje no es regular, NO ES REGULAR, es decir no nos sirve para probar que sea regular, sino mas bien solo para probar que no es regular.

Digamos que nuestro lenguaje L, es un lenguaje regular, entonces todas las cadenas que pertenezcan a L las podremos dividir en 3 SubStrings usando un numero n (que obviamente tiene que ser menor que la longitud del string original):

  • “y” no puede ser un string vacío: y ≠ε
  • La concatenación de los primeros dos tiene que ser menor que n: |xy| ≤ n
  • Para todas las cadenas con k ≥0, la cadena “x·y^k·z” también esta en el lenguaje L.

Esto es, en español que siempre podremos encontrar una y, no tal lejos del origen que puede ser “repetida o pumped” tantas veces como se quiera (incluso 0 con k=0) y que el string resultante esta aún en L.

 

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión /  Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión /  Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión /  Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión /  Cambiar )

Conectando a %s