1 Unidad 2 Ejemplos De ER LENGUAJES Y AUTOMATAS

LENGUAJES Y AUTOMATAS
2.2 OPERACIONES (EJEMPLOS )

Sea L = {0,11}.
L ͦ={Є}, independientemente de que lenguaje sea L; la potencia 0 representa
la selección de cero cadenas de L.

L¹={L}, representa la elección de una cadena L. Por tanto , los dos primeros términos de la expansión de L* nos da { Є,0,11}.

A continuación considere L². Seleccionamos dos cadenas de L, permitiendo repeticiones , demodo que tenemos cuatro posibilidades . Estas cuatro selecciones nos dan L²={00,011,110,1111}.

De forma similar , L³ es el conjunto de de cadenas que se pueden formar eligiendo tres posibilidades de las dos cadenas de L, lo que nos proporciona
{000,0011,0110,1100,01111,11011,11110,111111}
Para calcular L*, tenemos que calcular Lͥ para cada i y hallar la unión de todos estos lenguajes. L ͥ tiene2 ͥ miembros. Aunque cada L ͥ es finito, la unión de un numero infinito de términos L ͥ generalmente es un lenguaje infinito.
Por lo tanto tenemos que :
L* = L ͦ 𝗨 L¹ 𝗨 L² …


LENGUAJES Y AUTOMATAS
Construccion de expresiones regulares
Todos los tipos de algebras se inician con las expresiones elementales, que normalmente son constantes y/o variables. Las algebras nos permiten construir masexpresiones aplicando un cierto conjunto de operadores a las expresiones elementales y a las expresiones previamente construidas. Normalmente , también se necesitan algunos métodos que permitan agrupar operadores con sus operandos, tales como los paréntesis. Por ejemplo, la familiar algebra de la aritmética se inicia con constantes, como los números enteros y reales, mas las variables y seconstruyen expresiones mas complejas utilizando operadores aritméticos como + y X.
El algebra de las expresiones regulares sigue también este patrón,
Utilizando constantes y variables que representan lenguajes y operadores para las tres operaciones como unión, el punto y el asterisco.
El caso básico consta de tres partes.
1 Las constantes Є y ø son expresiones regulares, que representan a los lenguajes {Є } y ø , respectivamente.
Es decir, L(Є) = { Є } y L(ø) = ø.
2 Si a es cualquier símbolo, entonces a es una expresión regular. Esta expresión representa el lenguaje de {a}, Es decir, L(a)={a}.
Observe que utilizamos la fuente en negrita para indicar la expresión correspondiente a un símbolo.
3 Una variable, normalmente escrita en mayúsculas e itálicas, como L, representa cualquierlenguaje.
Paso Inductivo. Existen cuatro partes en el paso de la inducción, una para una cada uno de los 3 operadores y otra para la introducción de paréntesis.
1.- Si E y F son expresiones regulares, entonces E+F es una expresión regular que representa la unión de L(E) y L(F). Es decir , L(E+F) = L(E) U L(F).

2.- Si E y F son expresiones regulares, entonces EF o E.F es una expresión regular querepresenta la concatenación de L(E) y L(F). Es decir L(E)L(F).

3.- Si E es una expresión regular, entonces E* es una expresión regular, que representa la clausura de L(E).
Es decir, L(E*)=(L(E))*.

4.- Si E es una expresión regular, entonces (E), una E cerrada entre paréntesis, es también una expresión regular, que representa el mismo lenguaje que E.
Formalmente; L((E)) =L(E).








METODOLOGIADE DISENO DE LAS ER (Expresiones Regulares)
Al tratar de encontrar una ER para un lenguaje dado, mientras mas complejo es el lenguaje es obvio que resulta mas difícil encontrar por pura intuición dicha ER. En estos casos puede ser conveniente trabajar en forma metodica. Una técnica que funciona en muchos casos consiste en determinar primero la estructura de la ER, dejando unos huecos pendientespara resolver luego. Estos huecos, que llamaremos contextos, son también lenguajes para los que habrá que encontrar una ER.
Ejemplo.- Obtener una ER para el lenguaje en el alfabeto {a,b,c} en que las palabras contienen exactamente una vez dos b. Por ejemplo, las palabras aabb, babba, pertenecen al lenguaje, pero no aaba, abbba ni bbabb.
Para resolver este problema, expresamos primero la...