Gramaticas Regulares

GRAMTICAS
REGULARES
TEMARIO
Introduccin
Introduccin a los Autmatas Finitos
Conceptos Fundamentales de la Teora de Autmatas
Autmatas Finito Deterministas (AFD)
Autmatas Finitos No Deterministas (AFN)
Autmatas Finitos con Transicin -
Expresiones Regulares
El Algebra de la las Expresiones Regulares
Ejercicios
INTRODUCCIN
Gramticas regulares:
Son los lenguajes formales ms simples, en la jerarqua de
Chomsky se refiere a los lenguajes de tipo 3, aquellos que
pueden representarse mediante, autmatas finitos o
expresiones regulares.
TEMARIO
Introduccin
Ejercicios
INTRODUCCIN A LOS AUTMATAS

FINITOS
Definicin:
Un autmata finito o mquina de estado finito es un
modelo computacional que realiza cmputos en forma automtica
sobre una entrada para producir una salida.
Este modelo est conformado por un alfabeto, un conjunto de
estados finitos, una funcin de transicin, un estado inicial y un
conjunto de estados finales. Su funcionamiento se basa en una
funcin de transicin, que recibe a partir de un estado inicial una
cadena de caracteres pertenecientes al alfabeto, y que va leyendo
dicha cadena a medida que el autmata se desplaza de un estado a
otro, para finalmente detenerse en un estado final o de aceptacin,
que representa la salida.

FINITOS
Los autmatas finitos constituyen un modelo til para
muchos tipos de hardware y software. Por ejemplo:
1. Software para disear y probar el comportamiento de

circuitos digitales.
2. El analizador lxico de un compilador para tratar

identificadores, palabras clave y signos de puntuacin.
3. Software para explorar textos largos, o para determinar

el nmero de apariciones de palabras, frases u otros
patrones.

FINITOS
En la siguiente figura se muestra el modelo de autmata finito para el

interruptor. Como en todos los autmatas finitos, los estados estn
representados mediante crculos; en este ejemplo, hemos denominado
a los estados on y off. Los arcos entre los estados estn etiquetados con
las entradas, las cuales representan las influencias externas sobre el
sistema. Los dos arcos indican que, sea cual sea el estado en que se
encuentra el sistema, cuando recibe la entrada Pulsar pasa al otro
estado. Uno de los estados se designa como el estado inicial, el
estado en el que el sistema se encuentra inicialmente.

FINITOS
El estado inicial es apagado (off) y, por conveniencia, hemos

indicado el estado inicial mediante la palabra Inicio y una flecha.
A menudo es necesario especificar uno o ms estados como estado
final o "de aceptacin. Llegar a uno de estos estados despus de
una secuencia de entradas indica que dicha secuencia es correcta.
Por ejemplo, el estado (on) como estado de aceptacin, ya que en
dicho estado, el dispositivo que est siendo controlado por el
interruptor funciona. Normalmente, los estados de aceptacin se
indican mediante un crculo doble.

FINITOS
El trabajo de este autmata consiste en reconocer la palabra clave

then, por lo que necesita cinco estados, representando cada uno de
ellos la posicin dentro de dicha palabra que se ha alcanzado hasta
el momento. Estas posiciones se corresponden con los prefijos de la
palabra. El estado inicial se corresponde con la cadena vaca y
cada uno de los estados tiene una transicin a la siguiente letra de
la palabra then. El estado denominado then se alcanza cuando la
entrada est formada por todas las letras de dicha palabra. Puesto
que el trabajo de este autmata es indicar el reconocimiento de la
palabra then, podemos considerar dicho estado como el nico
estado de aceptacin.
TEMARIO
Introduccin
Ejercicios
ALFABETOS
Definicin:
Un alfabeto es un conjunto de smbolos finito y no vaco.
Convencionalmente, utilizamos el smbolo para designar
un alfabeto.
1) = {0,1}, el alfabeto binario.
2) = { a, b, . . . , z}, el conjunto de todas las letras
minsculas.
3) El conjunto de todos los caracteres ASCII o el conjunto
de todos los caracteres ASCII imprimibles.
CADENA DE CARACTERES
Definicin:
Una cadena de caracteres es una secuencia finita de
smbolos seleccionados de algn alfabeto. Por ejemplo,
01101 es una cadena del alfabeto binario = {0,1}. La
cadena 111 es otra cadena de dicho alfabeto.
LA CADENA VACA
Definicin:
La cadena vaca es aquella cadena que presenta cero
apariciones de smbolos. Esta cadena, designada por , es
una cadena que puede construirse en cualquier alfabeto.
LONGITUD DE CADENA
Definicin:
Es la longitud de la cadena, es decir, el nmero posiciones
ocupadas por los smbolos dentro de la cadena.
Por ejemplo, 01101 tiene una longitud de 5.
LONGITUD DE CADENA
Es habitual decir que la longitud de una cadena es igual al
nmero de smbolos que contiene; esta proposicin est
aceptada coloquialmente, sin embargo, no es estrictamente
correcta. As, en la cadena 01101 slo hay dos smbolos, 0 y
1, aunque tiene cinco posiciones para los mismos y su
longitud es igual a 5.
La notacin estndar para indicar la longitud de una
cadena w es |w|. Por ejemplo: Si w = 001
|w| = 3
||
=0
POTENCIAS DE UN ALFABETO
Definicin:
Si es un alfabeto, podemos expresar el conjunto de todas
las cadenas de una determinada longitud de dicho alfabeto
utilizando una notacin exponencial. Definimos ^k para
que sea el conjunto de las cadenas de longitud k, tales que
cada uno de los smbolos de las mismas pertenece a .
Observe que ^0 = { }, independientemente de cul sea el
alfabeto . Es decir, es la nica cadena cuya longitud es 0.
Si = {0,1}, entonces
^1 = {0,1}
^2 = {00,01,10,11}
^3 = {000,001,010,011,100,101,110,111}
Observe que existe una ligera confusin entre y ^1. El
primero es un alfabeto; sus elementos 0 y 1 son los smbolos.
Lo segundo es un conjunto de cadenas; sus elementos son
las cadenas 0 y 1, cuya longitud es igual a 1.
Por convenio, el conjunto de todas las cadenas de un
alfabeto se designa mediante *. Por ejemplo,
* = { ,0,1,00,01,10,11,000, . . .}.
Expresado de otra forma,
* = ^0 ^1 ^2
En ocasiones, desearemos excluir la cadena vaca del
conjunto de cadenas. El conjunto de cadenas no vacas
del alfabeto se designa como +. Por tanto:
+ = ^1 ^2 ^3
* = + { } * = + ^0
CONCATENACIN DE CADENAS
Definicin:
Sean x e y dos cadenas. Entonces, xy denota la
concatenacin de x e y, es decir, la cadena formada por
una copia de x seguida de una copia de y. Dicho de
manera ms precisa, si x es la cadena compuesta por i
smbolos x = a1a2 ai e y es la cadena compuesta por
j smbolos y = b1b2 bj , entonces xy es la cadena de

longitud xy = a1a2 aib1b2 bj.
CONCATENACIN DE CADENAS
Ejemplo:
Sean x = 01101 e y = 110.
Entonces xy = 01101110 e yx = 11001101.
Para cualquier cadena w, tenemos que:
w = w = w
Es decir, es el elemento neutro de la concatenacin, dado
que su concatenacin con cualquier cadena proporciona la
misma cadena como resultado.
LENGUAJES
Un conjunto de cadenas, todas ellas seleccionadas de un
*, donde es un determinado alfabeto se denomina
lenguaje. Si es un alfabeto y L *, entonces L es un
lenguaje de .
LENGUAJES
Ejemplos:
Un ejemplo sera el ingls, donde la coleccin de las

palabras correctas inglesas es un conjunto de cadenas del
alfabeto que consta de todas las letras.
Otro ejemplo es el lenguaje C, o cualquier otro lenguaje

de programacin, donde los programas correctos son un
subconjunto de las posibles cadenas que pueden formarse a
partir del alfabeto del lenguaje. Este alfabeto es un
subconjunto de los caracteres ASCII.
LENGUAJES
Ejemplos: Si = {0,1}
El lenguaje de todas las cadenas que constan de n ceros

seguidos de n unos para cualquier n 0:
{ ,01,0011,000111, . . .}.
El conjunto de cadenas formadas por el mismo nmero

de ceros que de unos: { ,01,10,0011,0101,1001, . . .}
El conjunto de nmeros binarios cuyo valor es un

nmero primo: {10,11,101,111,1011, . . .}
LENGUAJES
Curiosidades:
* es un lenguaje para cualquier alfabeto .
, el lenguaje vaco, es un lenguaje de cualquier alfabeto.
{ }, el lenguaje que consta slo de la cadena vaca,

tambin es un lenguaje de cualquier alfabeto. Observe
que { }; el primero no contiene ninguna cadena y el
segundo slo tiene una cadena.
LENGUAJES
Curiosidades:
La nica restriccin sobre un lenguaje es que todos los

alfabetos son finitos. De este modo, los lenguajes, aunque
pueden tener un nmero infinito de cadenas, estn
restringidos a que dichas cadenas estn formadas por los
smbolos que definen un alfabeto finito y prefijado.
LENGUAJES
Definicin del Lenguaje Mediante Descripciones de
Conjuntos:
Es habitual describir un lenguaje utilizando una descripcin
de conjuntos:
{w | algo acerca de w}
Esta expresin se lee el conjunto de palabras w tal que (lo
que se dice acerca de w a la derecha de la barra vertical).
LENGUAJES
Ejemplos:
{w | w consta de un nmero igual de ceros que de unos }.
{w | w es un entero binario que es primo }.
{w | w es un programa C sintcticamente correcto }.
LENGUAJES
Tambin es habitual reemplazar w por alguna expresin con
parmetros y describir las cadenas del lenguaje estableciendo
condiciones sobre los parmetros.
Ejemplo:
{0^n 1^n | n 1}.

Esta expresin se lee: El conjunto de 0 a la n y 1 a la n
tal que n es mayor o igual que 1, este lenguaje consta de
las cadenas {01,0011,000111, . . .}.
LENGUAJES
Ejemplo:
{0î1^j | 0 i j }.
Este lenguaje consta de cadenas formadas por ceros (puede
ser ninguno) seguidos de al menos el mismo nmero de unos.
TEMARIO
Introduccin
Ejercicios
AUTMATAS FINITOS DETERMINISTAS

(AFD)
Definicin:
Es aquel Autmata Finito que slo puede estar en un nico
estado despus de leer cualquier secuencia de entradas. El
trmino determinista hace referencia al hecho de que
para cada entrada slo existe uno y slo un estado al que el
autmata puede hacer la transicin a partir de su estado
actual.

(AFD)
Un autmata finito determinista consta de:
1.
Un conjunto finito de estados, a menudo designado como Q.
2.
Un conjunto finito de smbolos de entrada, se designa como .
3.
Una funcin de transicin que toma como argumentos un

estado y un smbolo de entrada y devuelve un estado.
4.
Un estado inicial, uno de los estados de Q.
5.
Un conjunto de estados finales F. El conjunto F es un

subconjunto de Q.

(AFD)
Entonces, definiremos un AFD utilizando la notacin de
siguiente:
A = (Q, , ,q0,F)
donde A es el nombre del AFD, Q es su conjunto de estados,
son los smbolos de entrada, es la funcin de transicin, q0 es el
estado inicial y F es el conjunto de estados finales.

(AFD)
Ejemplo:
Especificamos formalmente un AFD que acepte nicamente
todas las cadenas de ceros y unos que contengan la secuencia 01
en cualquier posicin de la cadena. Al que denominaremos con la
letra A.

(AFD)
Qu sabemos del autmata?
En primer lugar, sabemos que su alfabeto de entrada

es = {0,1}.
Tiene un determinado conjunto de estados, Q, siendo uno de

ellos, por ejemplo q0, el estado inicial.

(AFD)
1.
Ha ledo ya una subcadena 01. En caso afirmativo, aceptar

cualquier secuencia de entradas futura; es decir, slo se
encontrar en estados de aceptacin.
2.
Todava no ha ledo la secuencia 01, pero la entrada ms

reciente ha sido un 0, de manera que si ahora lee un 1, habr
ledo la subcadena 01 y podr aceptar cualquier cosa que lea de
ah en adelante
3.
Todava no ha ledo la secuencia 01, pero la ltima entrada

no existe (acaba de iniciarse) o ha sido un 1. En este caso, A no
puede aceptar la entrada hasta que no lea un 0 seguido
inmediatamente de un 1.

(AFD)
Cada una de las tres condiciones anteriores puede representarse

mediante un estado. La condicin (3) se representa
mediante el estado inicial, q0. Si estando en el estado q0 lo primero
que leemos es un 1, entonces no leeremos la secuencia 01 y, por
tanto, deberemos permanecer en el estado q0. Es decir, (q0,1) = q0.
Todava no ha ledo la secuencia 01, pero la ltima entrada no existe
(acaba de iniciarse) o ha sido un 1? En este caso, A no puede aceptar la
entrada hasta que no lea un 0 seguido inmediatamente de un 1.

(AFD)
Sin embargo, si estando en el estado q0 y a continuacin leemos un

0, nos encontraremos en el caso de la condicin (2). Por tanto,
utilizaremos q2 para representar la condicin (2). La transicin de
q0 para la entrada 0 es (q0,0) = q2.
Todava no ha ledo la secuencia 01, pero la entrada ms reciente ha sido

un 0, de manera que si ahora lee un 1, habr ledo la subcadena 01 y
podr aceptar cualquier cosa que lea de ah en adelante

(AFD)
Consideremos ahora las transiciones desde el estado q2. Si leemos

un 0, no mejoramos nuestra situacin pero tampoco la empeoramos.
El estado q2 describe esta situacin perfectamente, por lo que
deseamos que (q2,0) = q2.
Todava no ha ledo la secuencia 01, pero la entrada ms reciente ha sido

un 0, de manera que si ahora lee un 1, habr ledo la subcadena 01 y
podr aceptar cualquier cosa que lea de ah en adelante

(AFD)
Si nos encontramos en el estado q2 y leemos una entrada 1, entonces

disponemos de un 0 seguido de un 1. Ahora podemos pasar a un
estado de aceptacin, que denominaremos q1, y que se corresponde
con la condicin (1). Es decir, (q2,1) = q1.
Ha ledo ya una subcadena 01? En caso afirmativo, aceptar cualquier

secuencia de entradas futura; es decir, slo se encontrar en estados de
aceptacin.

(AFD)
Por ltimo, tenemos que disear las transiciones para el estado q1.
En este estado, ya hemos ledo una secuencia 01, as que,
independientemente de lo que ocurra, nos encontraremos en una
situacin en la que hemos ledo la secuencia 01.
Es decir, (q1,0) = q1 y (q1,1) = q1.
Ha ledo ya una subcadena 01? En caso afirmativo, aceptar cualquier
secuencia de entradas futura; es decir, slo se encontrar en estados de
aceptacin.

(AFD)
Por tanto, Q = {q0,q1,q2}.
Como hemos dicho, q0 es el estado inicial y el nico estado de
aceptacin es q1; es decir, F = {q1}.
La especificacin completa del autmata A que acepta el lenguaje
L de cadenas que contienen una subcadena 01 es
A = ( { q0 , q1 , q2 } , { 0 , 1 } , , q0 , { q1 } )

(AFD)
Tablas de Transiciones
Una tabla de transiciones es una representacin tabular
convencional de una funcin que toma dos argumentos y devuelve
un valor. Las filas de la tabla corresponden a los estados y las
columnas a las entradas. La entrada para la fila correspondiente
al estado q y la columna correspondiente a la entrada a es el
estado (q,a).

(AFD)

(AFD)
Extensin a cadenas de la funcin de transicin
Si es la funcin de transicin, entonces la funcin de transicin
extendida construida a partir de ser ^ . La funcin de
transicin extendida es una funcin que toma un estado q y una
cadena w y devuelve un estado p (el estado al que el autmata
llega partiendo del estado q y procesando la secuencia de
entradas w).

(AFD)
Definimos ^ por induccin sobre la longitud de la cadena de
entrada como sigue:
Base: ^ (q,) = q. Es decir, si nos encontramos en el estado

q y no leemos ninguna entrada, entonces permaneceremos
en el estado q.

(AFD)
Paso Inductivo: Supongamos que w es una cadena de la forma xa; es decir,

a es el ltimo smbolo de w y x es la cadena formada por todos los
smbolos excepto el ltimo.
Por ejemplo, w = 1101 se divide en x = 110 y a = 1.
Luego: (^(q , x), a) = q
(p, a) = q

(AFD)
Ejemplo:
Supongamos que tenemos el lenguaje
L = {w | w tiene un nmero par de ceros y un nmero par de unos}
q0: tanto el nmero de ceros como el de unos ledos hasta el momento es par.
q1: el nmero de ceros ledos hasta el momento es par, pero el de unos es
impar.
q2: el nmero de unos ledos hasta el momento es par, pero el de ceros es
impar.
q3: tanto el nmero de ceros como el de unos ledos hasta el momento es
impar.

(AFD)
El estado q0 es tanto el estado inicial como el nico estado de
aceptacin. Es el estado inicial porque antes de leer ninguna
entrada, la cantidad de ceros y unos ledos hasta el momento es
igual a cero y cero es par. Ahora ya sabemos cmo especificar el
AFD para el lenguaje L.
As A = ( { q0 , q1 , q2 , q3 } , { 0 , 1 } , , q0 , { q0 } )

(AFD)
Ejemplo:
Supongamos que la entrada es 110101.
Dado que esta cadena tiene un nmero par de ceros y unos,
podemos asegurar que pertenece al lenguaje. As, tendremos que
(q0,110101) = q0, ya que q0 es el nico estado de aceptacin.
Verifiquemos ahora esta afirmacin.
La comprobacin supone calcular (q0,w) para cada prefijo w de
110101, comenzando por y aumentando progresivamente el
tamao. El resumen de este clculo es:

(AFD)
Ejemplo: 110101
( q0 , ) = q0.
( q0 , 1 ) = ( (q0 , ) , 1 ) = ( q0 , 1 ) = q1.
( q0 ,11 ) = ( (q0 , 1 ) ,1 ) = ( q1 , 1 ) = q0.
( q0 , 110 ) = ( (q0 , 11 ) , 0 ) = ( q0 , 0 ) = q2.
( q0 , 1101 ) = ( (q0 , 110 ) , 1 ) = ( q2 , 1 ) = q3.
( q0 , 11010 ) = ( (q0 , 1101 ) , 0 ) = ( q3 , 0 ) = q1.
( q0 , 110101 ) = ( (q0 , 11010 ) , 1 ) = ( q1 , 1 ) = q0.
TEMARIO
Introduccin
Ejercicios
AUTMATAS FINITOS NO
DETERMINISTAS (AFN)
Al igual que el AFD, un AFN tiene un conjunto finito de estados,
un conjunto finito de smbolos de entrada, un estado inicial y un
conjunto de estados de aceptacin. La diferencia entre los AFD y
los AFN se encuentra en el tipo de funcin . En los AFN, es
una funcin que toma un estado y smbolos de entrada como
argumentos, pero devuelve un conjunto de cero, uno o ms
estados (en lugar de devolver exactamente un estado como lo
hacen los AFD).
AUTMATAS FINITOS NO
DETERMINISTAS (AFN)
Ejemplo:
A continuacin se muestra un autmata finito no determinista,
cuyo trabajo consiste en aceptar todas las cadenas formadas por
ceros y unos que terminan en 01.
AUTMATAS FINITOS NO
DETERMINISTAS (AFN)
Ejemplo: Vamos a probar la cadena 00101
AUTMATAS FINITOS NO
DETERMINISTAS (AFN)
Equivalencia de un AFD y un AFN
Todo lenguaje que puede describirse mediante algn AFN
tambin puede ser descrito mediante algn AFD.
El AFD en la prctica tiene aproximadamente tantos estados
como el AFN, aunque a menudo tiene ms transiciones.
En el caso peor, el AFD puede tener 2^n estados mientras que el
AFN ms pequeo para el mismo lenguaje tiene slo n estados.
AUTMATAS FINITOS NO
DETERMINISTAS (AFN)
Ejemplo:
Sea N el autmata que acepta todas las cadenas de nmeros
binarios que terminan en 01. Dado que el conjunto de estados de
N es {q0,q1,q2}, la construccin del subconjunto de estados para
un AFD da como resultado 2^3 = 8 estados, correspondientes a
todos los subconjuntos de estos tres estados.
AUTMATAS FINITOS NO
DETERMINISTAS (AFN)
AUTMATAS FINITOS NO
DETERMINISTAS (AFN)
TEMARIO
Introduccin
Ejercicios
AUTMATAS FINITOS CON

TRANSICIN -
Esta nueva caracterstica de los autmata finito nos permite
transiciones para , la cadena vaca. As, un AFN puede hacer
una transicin espontneamente, sin recibir un smbolo de
entrada. Esta nueva capacidad no expande la clase de lenguajes
que los autmatas finitos pueden aceptar, pero proporciona
algunas facilidades de programacin.

TRANSICIN -
Podemos representar un AFN- del mismo modo que
representaramos un AFN con una excepcin: la funcin de
transicin tiene que incluir la informacin sobre las transiciones
para . Formalmente, representamos un AFN- A mediante
A = (Q, , ,q0,F), donde todos los componentes tienen la misma
interpretacin que en un AFN, excepto que ahora es una
funcin que toma como argumentos:
1.
Un estado de Q y,
2.
Un elemento de { }, es decir, un smbolo de entrada o el

smbolo . Es preciso que , no pueda ser un elemento del
alfabeto , con el fin de que no se produzcan confusiones.

TRANSICIN -
Ejemplo: Autmata que acepte la palabra web o ebay

TRANSICIN -
Ejemplo:

TRANSICIN -
Clausura Respecto de
La clausura respecto de de un estado q se realiza siguiendo
todas las transiciones salientes de q que estn etiquetadas
con . Sin embargo, cuando obtenemos los otros estados
siguiendo , seguimos las transiciones- salientes de
dichos estados, y as sucesivamente, hasta encontrar todos los
estados a los que se puede llegar desde q siguiendo
cualquier camino cuyos arcos estn etiquetados con .

TRANSICIN -
Clausura Respecto de
Formalmente, la clausura respecto de ,CLAUSURA(q),
se define recursivamente de la forma siguiente:
Base: El estado q pertenece a CLAUSURA (q).
Paso Inductivo: Si el estado p pertenece a CLAUSURA (q) y

existe una transicin desde el estado p al estado r etiquetada
con , entonces r pertenece a CLAUSURA (q). De forma ms
precisa, si es la funcin de transicin del AFN- y p pertenece
a CLAUSURA (q), entonces CLAUSURA (q) tambin contiene
todos los estados de (p,).

TRANSICIN -
Ejemplo:
CLAUSURA (1) = {1,2,3,4,6}

TRANSICIN -
Eliminacin de las transiciones-
Dado cualquier AFN- E, podemos hallar un AFD D que acepte
el mismo lenguaje que E. La construccin que empleamos es muy
parecida a la construccin de subconjuntos de un AFN a un AFD,
ya que los estados de D son subconjuntos de los estados de E. La
nica diferencia es que tenemos que incorporar las transiciones-
de E, lo que hacemos a travs del mecanismo de clausura
respecto de .

TRANSICIN -
TEMARIO
Introduccin
Ejercicios
EXPRESIONES REGULARES
Definicin:
Una expresin regular, es una secuencia de caracteres que
forma un patrn de bsqueda, principalmente utilizada para la
bsqueda de patrones de cadenas de caracteres u operaciones de
sustituciones.
Las expresiones regulares estn estrechamente relacionadas con
los autmatas finitos no deterministas y pueden considerarse
una alternativa. Pueden definir de forma exacta los mismos
lenguajes que describen los distintos tipos de autmatas. Sin
embargo, las expresiones regulares ofrecen algo que los
autmatas no proporcionan: una forma declarativa para expresar
las cadenas que deseamos aceptar. Por tanto, las expresiones
regulares sirven como lenguaje de entrada de muchos sistemas
que procesan cadenas.
Operaciones de las Expresiones Regulares
Unin:
La unin de dos lenguajes L y M, designada como L M, es el
conjunto de cadenas que pertenecen a L, a M o a ambos.
Ejemplo:
L = {001,10,111}
M = {,001}
entonces L M = {,10,001,111}
Concatenacin
La concatenacin de los lenguajes L y M es el conjunto de
cadenas que se puede formar tomando cualquier cadena de L y
concatenndola con cualquier cadena de M. Para designar la
concatenacin de lenguajes se emplea el punto o ningn
operador.
Concatenacin
Ejemplo:
L={001,10,111}
M = { ,001}
entonces L.M = {001,10,111,001001,10001,111001}
Las tres primeras cadenas de L.M son las cadenas de L
concatenadas con . las tres ltimas cadenas de L.M se forman
tomando cada una de las cadenas de L y concatenndolas con la
segunda cadena de M, que es 001.
Clausura o Clausura de Kleene
La clausura de un lenguaje L se designa mediante L* y
representa el conjunto de cadenas que se pueden formar tomando
cualquier nmero de cadenas de L y concatenando todas ellas.
Clausura o Clausura de Kleene
Ejemplo:
Si L = {0,1} entonces L* es igual a todas las cadenas de 0s y 1s.
Si L = {0,11} entonces L* es igual a todas cadenas de 0s y 1s tales

que los 1s aparezcan por parejas: 011, 11110
L* es la unin infinita i0 Lî donde

L^0 = { }
L^1 = L
Lî, para i > 1 es LL L (la concatenacin de i copias de L).
TEMARIO
Introduccin
Ejercicios
Conmutatividad
Esta ley establece que podemos efectuar la unin de dos
lenguajes en cualquier orden.
Por ejemplo: L + M = M + L
EL ALGEBRA DE LA LAS EXPRESIONES
Asociatividad de la unin
Esta ley, establece que podemos efectuar la unin de tres
lenguajes bien calculando primero la unin de los dos primeros, o
bien la unin de los dos ltimos.
Por ejemplo: (L + M) + N = L + (M + N)
Asociatividad para la concatenacin
Esta ley, establece que podemos concatenar tres lenguajes
concatenando primero los dos primeros o bien los dos ltimos.
Por ejemplo: (LM)N = L(MN)
Elemento Identidad y Elemento Nulo

El elemento identidad de un operador es un valor tal que cuando
el operador se aplica al propio elemento identidad y a algn otro
valor, el resultado es ese otro valor. Por ejemplo, 0 es el elemento
identidad para la suma, ya que 0+x= x+0 = x, y 1 es el elemento
identidad de la multiplicacin, puesto que 1x= x1 = x.
El elemento nulo de un operador es un valor tal que cuando el
operador se aplica al propio elemento nulo y a algn otro valor, el
resultado es el elemento nulo. Por ejemplo, 0 es el elemento nulo
de la multiplicacin, ya que 0x = x0 = 0.
Elemento Identidad y Elemento Nulo

Existen tres leyes para las expresiones regulares:
+ L = L + = L. Esta ley establece que es el elemento

identidad para la unin.
L = L = L. Esta ley establece que es el elemento identidad

para la concatenacin.
L = L = . Esta ley establece que es el elemento nulo de

la concatenacin.
Leyes Distribuidas
Una ley distributiva implica a dos operadores y establece que un
operador puede aplicarse por separado a cada argumento del otro
operador.
L(M + N) = LM + LN. sta es la ley distributiva por la

izquierda de la concatenacin respecto de la unin.
(M + N)L = ML + NL. sta es la ley distributiva por la derecha

de la concatenacin respecto de la unin.
Ley de Idempotencia
Se dice que un operador es idempotencia si el resultado de
aplicarlo a dos valores iguales es dicho valor. Por tanto, para
expresiones regulares, podemos establecer la siguiente ley:
L + L = L. sta es la ley de idempotencia para la unin, que

establece que si tomamos la unin de dos expresiones idnticas,
podemos reemplazarla por una copia de la de la expresin.
Leyes Relativas a la Clausura
(L*)* = L*. Esta ley dice que clausurar una expresin que ya
est clausurada no modifica el lenguaje. El lenguaje de (L*)* est
formado por todas las cadenas creadas mediante la
concatenacin de cadenas pertenecientes al lenguaje L*. Pero
dichas cadenas estn formadas a su vez por cadenas de L. Por
tanto, la cadena perteneciente a (L*)* tambin es una
concatenacin de cadenas de L y, por tanto, pertenece al lenguaje
de L*.
* = . La clausura de slo contiene la cadena

* = . Es fcil comprobar que la nica cadena que se puede
formar concatenando cualquier nmero de copias de la cadena
vaca es la propia cadena vaca.
L* = (L+) + . La demostracin es fcil, ya que la expansin de

L+ incluye cada uno de los trminos de la expansin de L*
excepto .

L+ = LL* = L*L
Recuerde que L+ se define para ser L+LL+LLL+ .
que, L* = +L+LL+ LLL+
Por tanto:
LL* = L +LL+LLL+LLLL+
Teniendo en cuenta que L = L, vemos que las expansiones
infinitas para LL* y para L+ son iguales.
Esto demuestra que L+ = LL*
Procedencia de los Operadores

El operador asterisco (*) es el de precedencia ms alta. Es decir,
se aplica slo a la secuencia ms corta de smbolos a su izquierda
que constituye una expresin regular bien formada.

El siguiente en precedencia es el operador de concatenacin,
punto. Despus de aplicar todos los operadores a sus
operandos, aplicamos los operadores de concatenacin a sus
operandos. Dado que la concatenacin es una operacin
asociativa, no importa en qu orden se realicen las sucesivas
concatenaciones, aunque si hay que elegir, las aplicaremos por la
izquierda.
Por ejemplo, 012 se aplica as: (01)2.

Ejemplo:
La expresin 01*+1 se aplica de la forma siguiente: 0(1*)+1. El
operador (*) se aplica en primer lugar. A continuacin,
realizamos las concatenaciones entre 0 y (1*), obteniendo la
expresin 0(1*) . Por ltimo, el operador de unin (+) se aplica
entre la ltima expresin y la que est a su derecha, que es 1.

Por ltimo, se aplican todos los operadores de unin (+) a sus
operandos. Dado que la unin tambin es asociativa, de nuevo no
importa en que orden se lleven a cabo, pero supondremos que se
calculan empezando por la izquierda.
TEMARIO
Introduccin
Ejercicios
EJERCICIOS
Autmatas Finitos Deterministas (AFD)
Describa los AFD que aceptan los siguientes lenguajes con
el alfabeto {0,1}:
1.
2.
El conjunto de todas las cadenas que terminan en 00.

El conjunto de todas las cadenas con tres ceros
consecutivos (no necesariamente al final).
3.
El conjunto de cadenas que contengan la subcadena 011.
4.
El conjunto de cadenas que empiecen o terminen (o ambas

cosas) con 01.
EJERCICIOS
1.
El conjunto de cadenas del alfabeto {0,1, . . . ,9} tal que el

dgito final haya aparecido antes en la misma entrada.
2.
El conjunto de cadenas del alfabeto {0,1, . . .,9} tal que el

dgito final no haya aparecido antes.
3.
El conjunto de cadenas formadas por ceros y unos tal que

contengan dos ceros separados por una cantidad de
posiciones que es mltiplo de 4. Observe que 0 es un
mltiplo permitido de 4.
EJERCICIOS
Escriba expresiones regulares para los siguientes lenguajes:
1.
El conjunto de cadenas del alfabeto {a,b,c} que contienen

al menos una a y al menos una b.
2.
El conjunto de cadenas formadas por 0s y 1s con a lo sumo

una pareja de 1s consecutivos.
3.
El conjunto de todas las cadenas formadas por ceros y

unos tales que cada pareja de 0s adyacentes aparece antes
que cualquier pareja de 1s adyacentes.
4.
El conjunto de todas las cadenas formadas por ceros y

unos que contienen 101 como subcadena.
EJERCICIOS
Proporcione las descripciones informales de los lenguajes
correspondientes a las siguientes expresiones regulares:
1.
(1+ )(00*1)*0+
2.
(0*1*)*000(0+1)*
3.
(0+10)*1*
EJERCICIOS
Algebra de Expresiones Regulares
Demuestre si cada una de las siguientes proposiciones
acerca de expresiones regulares es verdadera o falsa.
1.
(R+S)* = R*+S*
2.
(RS+R)*R = R(SR+R)*
3.
(RS+R)*RS = (RR*S)*
4.
(R+S)*S = (R*S)*
5.
S(RS+S)*R = RR*S(RR*S)*

Gramaticas Regulares

Cargado por

Copyright:

Formatos disponibles

Gramaticas Regulares

Cargado por

Información del documento

Descripción original:

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Gramaticas Regulares

Cargado por

Copyright:

Formatos disponibles

GRAMTICAS

Introduccin a los Autmatas Finitos

Conceptos Fundamentales de la Teora de Autmatas

Autmatas Finito Deterministas (AFD)

Autmatas Finitos No Deterministas (AFN)

Autmatas Finitos con Transicin -

El Algebra de la las Expresiones Regulares

Introduccin a los Autmatas Finitos

Conceptos Fundamentales de la Teora de Autmatas

Autmatas Finito Deterministas (AFD)

Autmatas Finitos No Deterministas (AFN)

Autmatas Finitos con Transicin -

El Algebra de la las Expresiones Regulares

INTRODUCCIN A LOS AUTMATAS

INTRODUCCIN A LOS AUTMATAS

1. Software para disear y probar el comportamiento de

2. El analizador lxico de un compilador para tratar

3. Software para explorar textos largos, o para determinar

INTRODUCCIN A LOS AUTMATAS

En la siguiente figura se muestra el modelo de autmata finito para el

INTRODUCCIN A LOS AUTMATAS

El estado inicial es apagado (off) y, por conveniencia, hemos

INTRODUCCIN A LOS AUTMATAS

El trabajo de este autmata consiste en reconocer la palabra clave

Introduccin a los Autmatas Finitos

Conceptos Fundamentales de la Teora de Autmatas

Autmatas Finito Deterministas (AFD)

Autmatas Finitos No Deterministas (AFN)

Autmatas Finitos con Transicin -

El Algebra de la las Expresiones Regulares

j smbolos y = b1b2 bj , entonces xy es la cadena de

Un ejemplo sera el ingls, donde la coleccin de las

Otro ejemplo es el lenguaje C, o cualquier otro lenguaje

El lenguaje de todas las cadenas que constan de n ceros

El conjunto de cadenas formadas por el mismo nmero

El conjunto de nmeros binarios cuyo valor es un

* es un lenguaje para cualquier alfabeto .

, el lenguaje vaco, es un lenguaje de cualquier alfabeto.

{ }, el lenguaje que consta slo de la cadena vaca,

La nica restriccin sobre un lenguaje es que todos los

{w | w consta de un nmero igual de ceros que de unos }.

{w | w es un entero binario que es primo }.

{w | w es un programa C sintcticamente correcto }.

{0^n 1^n | n 1}.

Introduccin a los Autmatas Finitos

Conceptos Fundamentales de la Teora de Autmatas

Autmatas Finito Deterministas (AFD)

Autmatas Finitos No Deterministas (AFN)

Autmatas Finitos con Transicin -

El Algebra de la las Expresiones Regulares

AUTMATAS FINITOS DETERMINISTAS

AUTMATAS FINITOS DETERMINISTAS

Un conjunto finito de estados, a menudo designado como Q.

Un conjunto finito de smbolos de entrada, se designa como .

Una funcin de transicin que toma como argumentos un

Un estado inicial, uno de los estados de Q.

Un conjunto de estados finales F. El conjunto F es un

AUTMATAS FINITOS DETERMINISTAS

AUTMATAS FINITOS DETERMINISTAS