LENGUAJES Y EXPRESIONES

[pic 1][pic 2]

INSTITUTO TECNOLÓGICO DE ACAPULCO

CARRERA; INGENIERÍA EN SISTEMAS COMPUTACIONALES

MATERIA;

LENGUAJES Y AUTÓMATAS 1

HORA; 3:00 PM A 4:00 PM

ALUMNO: ALFREDO MORALES MEDINA

NUMERO DE CONTROL: 18320930

SEMESTRE; 5

TRABAJO UNIDAD 1, CONTROL DE LECTURA CAPITULO 3(LENGUAJES Y EXPRESIONES

REGULARES)

07 DE SEPTIEMBRE DE 2020 EN ACAPULCO DE JUAREZ

Capítulo 3 LENGUAJES Y EXPRESIONES

REGULARES

1 expresiones regulares

Las expresiones regulares son una serie 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. El objetivo de las expresiones regulares es representar todos los posibles lenguajes definidos sobre un alfabeto Σ, en base a una serie de lenguajes primitivos, y unos operadores de composición.

Dado un alfabeto Σ, las expresiones regulares sobre Σ se definen de forma recursiva por las siguientes reglas.

1.2 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. Antes de describir la notación de las expresiones regulares, tenemos que estudiar las tres operaciones sobre los lenguajes que representan los operadores de las expresiones regulares. Estas operaciones son:

1.La unión de dos lenguajes L y M, designada como L ∪ M, es el conjunto de cadenas que pertenecen a L, a M o a ambos. Por ejemplo, si L={001,10,111} y M = {ε ,001}, entonces L ∪ M = {ε ,10,001,111}.

2.La concatenación de los lenguajes L y M es el conjunto de cadenas que se puede formar tomando cualquier cadena de L y concentrándola con cualquier cadena de M. Para designar la concatenación de lenguajes se emplea el punto o ningún operador en absoluto, aunque el operador de concatenación frecuentemente se llama “punto”. Por ejemplo, si L={001,10,111} y M = {ε ,001}, entonces L.M, o simplemente LM, es {001,10,111,001001,10001,111001}. Las tres primeras cadenas de LM son las cadenas de L concatenadas con ε . Puesto que ε es el elemento identidad para la concatenación, las cadenas resultantes son las mismas cadenas de L. Sin embargo, las tres últimas cadenas de LM se forman tomando cada una de las cadenas de L y concatenándolas con la segunda cadena de M, que es 001.

3.La clausura (o asterisco, o clausura de Kleene) de un lenguaje L se designa mediante L^*y representa el conjunto de cadenas que se pueden formar tomando cualquier número de cadenas de L, posiblemente con repeticiones (es decir, la misma cadena se puede seleccionar más de una vez) y concatenando todas ellas. Por ejemplo, si L = {0,1}, entonces L^*es igual a todas las cadenas de 0s y 1s. Si L = {0,11}, entonces L^(* )constará de aquellas cadenas de 0s y 1s tales que los 1s aparezcan por parejas, como por ejemplo 011,11110 y ε , pero no 01011 ni 101. Más formalmente, L* es la unión infinita ∪(i≥0) L^i, donde L^0=(ε),L^1=L y L^i, para i>1 es LL• • •L (la concatenación de i copias de L).

1.3 CONSTRUCCIÓN DE EXPRESIONES REGULARES

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 {a}. Es decir, L(a)={a}.

3.Una variable, normalmente escrita en mayúsculas e itálicas, como L, representa cualquier lenguaje.

Existen cuatro partes en el paso de inducción, una para cada uno de los tres operadores y otra para la introducción de paréntesis.

...