lenguajes regulares

1. LENGUAJES REGULARES

Definición

Sea un alfabeto, el conjunto de lenguajes regulares sobre el alfabeto se define como sigue:

 es un lenguaje regular
 es un lenguaje regular
Para toda a є al alfabeto,{a} es un lenguaje regular
Si L1 y L2 son dos lenguajes regulares, entonces L1 U L2, L1 * L2 y L1* son lenguajes regulares
Ningun otro lenguaje sobre el alfabeto es regularEjemplo 1
Sea Σ={a,b}, entonces de la definición se tiene que:
 y  son regulares
 son regulares
 es regular (union)
 son regulares (Concatenacion)
 Es regular (Union)

Ejemplo 2
Sea Σ={0,1,2}, entonces de la definición se tiene que:
 y  son regulares
 son regulares
 es regular (union)
son regulares (Concatenacion)

Teoremas
Todos los lenguajes finitos sonregulares
Si L es regular,entonces  también es regular.
Si L1 y L2 son regulares, Entonces L1 ∩ L2, L1 – L2, L2-L1 tambien son lenguajes regulares.


2.1. Gramáticas regulares

2.2. Autómatas finitos deterministas

Diagramas de transiciones

Las expresiones regulares nos permiten determinar con facilidad si una cadena pertenece o no a un lenguaje dado. Por ejemplo: si tenemos al lenguajedefinido por la expresión regular a*b*, esta se puede interpretar como el lenguaje que acepta cualquier cadena que comience con cualquier cantidad de aes, seguida por cualquier cantidad de bes, como por ejemplo: aaab,abbb,a,bb,ε,etc. Pero en cambio, no acepta otras cadenas como abab,baba,bba,etc.

Otra técnica que permite identificar si una cadena es aceptada o no por un lenguaje es el empleo dediagramas de transiciones, los cuales son grafos dirigidos a cuyos nodos se les llama estados y a sus aristas se las llama transiciones, estas se encuentran etiquetadas con algún símbolo del alfabeto, como se muestra en la figura siguiente.







Existe un estado que se llama estado inicia, el cual se señala con una flecha, a partir del cual se comienza el reconocimiento de la cadena;cada símbolo leído provoca una transición de un estado a otro, siguiendo la arista etiquetada con este. Este proceso se repite hasta agotar la cadena. Si el estado donde finalizamos es un estado de aceptación, que se identifica por un doble circulo, quiere decir que la cadena analizada pertenece al lenguaje, en caso contrario es rechazada.

Ejemplo 1:
La siguiente figura nos permite observarcómo se emplea el diagrama de transiciones anterior para determinar si la cadena w=aaabab es aceptada o no por el lenguaje representado por este.



Y como el terminal no es de aceptación la cadena es rechazada

En cambio si la cadena es w=aaababb es una cadena valida por que el terminal es de aceptación.

También es posible representar un diagrama de transiciones de manera tabular de lasiguiente forma: colocamos a cada símbolo como encabezado de una de las columnas y a cada estado al inicio de cada uno de los renglones. La flecha indica el estado inicial y el asterisco se usa para denotar los estados de aceptación. Dentro de la tabla se coloca el estado siguiente según corresponda cada transición:


a
b

q0
q1
q1
q1
q0







Autómata finito determinista

Es elmodelo matemático de un sistema. Al modelo matematico que hemos definido por medio de un diagrama de transiciones, que presenta a una maquina que pasa de un estado a otro como respuesta a cada uno de los símbolos de una cadena de entrada, se le llama autómata finito determinista y se denota por AFD.

Formalmente se define a un AFD por la quíntupla M=(Q,,t,s,F) donde Q es un conjunto finito deestados, es el alfabeto de entrada, s es el estado inicial que pertenece a Q, t es la función de transición y F es el subconjunto de Q de los estados de aceptación.

La característica principal de un AFD es que t es una función que esta definida para todos los posibles estados de qi que pertenecen a Q y para todos los simbolos que pertenecen al alfabeto. Es decir para cualquier pareja de la...