Lo Nuevo

Buenas tardes

Para este corte el trabajo de investigación consiste en:

* Investigar sobre Teoría de la computación y sus aplicaciones
* Dar una explicación clara y detallada de: Lenguajes regulares y expresiones regulares. ( averigüen acerca de la clausura de Kleene).

El trabajo de investigación debe ser entregado con las normas correspondientes (bibliografía, introducción, etc).Teoría de la Computación

Lenguajes regulares
Los conjuntos regulares son aquellos que se pueden construir utilizando las operaciones de concatenación unión y cierre de Kleene, en un orden arbitrario, a partir del conjunto vacío, la cadena vacía y los conjuntos unitarios. Veremos que los conjuntos regulares son aquellos que se pueden reconocer utilizando autómatas finitos.
Un lenguaje L sedenomina regular si y solo si existe un autómata finito determinista A tal que L=L(A). Se pueden dar definiciones equivalentes, utilizando expresiones regulares o gramáticas regulares, ya que estos formalismos definen la misma clase de lenguajes:

No todos los lenguajes son regulares.

Los autómatas finitos solo tienen una capacidad limitada en el proceso de identificación de palabras:

*Tienen un numero limitado de estados
* La única información de la que disponen esta en la estructura de este numero finito de estados

Ejemplo:

El lenguaje L={anbn|n>=0} no es regular.

Se requería un autómata reconocedor con infinitos estados para aceptar este lenguaje, por lo que no puede ser regular.

Construir de manera incremental los AFD para los siguientes lenguajes:

*L0={l}
* L1={l,ab}
* L2={l,ab,aabb}
* L3={l,ab,aabb,aaabbb}
* ...bv

* Se puede observar que el número de estados de los autómatas aumenta para cada uno de estos lenguajes.
* No es posible encontrar autómatas finitos deterministas, tales que el número de estados no aumente de un lenguaje Li al siguiente Li+1.
* Eso indica que el autómata que reconoce el lenguaje Lrequiere un numero infinito de estados.

Teorema:
El lenguaje L (A) aceptado por el autómata finito A es el mismo que el lenguaje L(G) representado por la gramática lineal por la izquierda G.
Demostración: Sea x =abc….d una cadena de símbolos terminales que pertenece al lenguaje L(G). Entonces, S * x. Al ser G una gramática lineal por la izquierda, la derivación de x tiene que tener laforma siguiente.
S Dd …. Cc…d Bbc… d abc … d
Luego en el conjunto de reglas de producción P de la gramática G tienen que existir las siguientes reglas:
S :: = Dd
…
C::= Bd
B::=a
En el autómata A se verifica que:

Por construcción del autómata A, dado que en G existe la regla de producción B ::= Bd debe cumplirse que . Luego

Por construcción del autómata A,dado que G existe la regla de producción C::= Bb, debe cumplirse que . Luego

Y así sucesivamente, hasta que al final
(p,x) = (D, d)
Por construcción del automata A, dado que en G existe la regla de produccion S::=Dd debe cumplirse que (D,d) = S.Luego
* (p,x) = S
Es decir, la cadena x conduce al autómata A a su único estado final S. Luego dicha cadena es aceptada por el autómata. Enconclusión: si x L(G), entonces x L(A).
Dado un autómata finito no determinista cualquiera, es posible construir un autómata finito determinista que acepta el mismo lenguaje. Además se demostró que dada la gramática lineal por derecha cualquiera, existe otra lineal por la izquierda equivalente. Por lo tanto, combinando estos tres datos se deduce lo siguiente: Dada cualquier gramática del tipo 3 deChomsky, es posible construir aun autómata finito determinista que acepte el mismo lenguaje representado por gramática

Expresiones regulares
El concepto de expresión regular fue introducido por Kleene en 1956 para describir los lenguajes aceptados por autómatas finitos.
Definición 2: Las expresiones regulares representan lenguajes regulares y su propósito es simplificar la escritura de los...