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 regular

Ejemplo 1 Sea Σ={a,b}, entonces de la definición se tiene que:

∅ y {ε } son regulares {a } y {b } son regulares {a ,b } es regular (union) {aa }, {ab } , {bb }, {ba } son regulares (Concatenacion) {a ,b ,ab ,ba ,aa ,bb } Es regular (Union)

Ejemplo 2Sea Σ={0,1,2}, entonces de la definición se tiene que:

∅ y {ε } son regulares {0 }, {1 } y {2 } son regulares {0,1,2 } , {0,1 } ,{0,2} es regular (union) {01 } , {12 }, {02 }son regulares (Concatenacion)

Teoremas Todos los lenguajes finitos son regulares Si L es regular,entonces LC=Σ¿−L 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 lenguaje definido 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.

q0 q1a

ba

b

Otra técnica que permite identificar si una cadena es aceptada o no por un lenguaje es el empleo de diagramas 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 observar có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.

q0→q0→q0→q0→q1→q1→q0

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 la siguiente 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 q0 q1

q1 q1 q0

b

q0 q1a

ba

Autómata finito determinista

Es el modelo 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 de estados, Σ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 forma que qi,simbolos siempre existe un único estado siguiente.

Ejemplo 1Sea M el AFD donde Q={q0,q1}, Σ={a,b}, F={q0}, s=q0 y las siguientes transiciones t(q0,a)=q0,t(q0,b)=q1;t(q1,a)=q1 y t(q1,b)=q0 esto se representa en la siguiente tabla de transiciones.

a b→q0 q0 q1

q1 q1 q0

Y el diagrama de transiciones quedaría

2.3. Autómatas finitos no deterministas

Automata finito no determinista es aquel que puede tener cero, una o mas transiciones distintas para el mismo símbolo de entrada y lo denotamos por AFN.

En algunas ocasiones resulta mucho mas practico emplear un AFN en vez de un AFD, tal como se puede observar en los siguientes ejemplos.

Ejemplo 1Considere al diagrama mostrado en la figura siguiente este representa a un AFN que acepta el lenguaje a*b Uab* se podrá observar que para algunos casos no existen transiciones definidas para otros hay mas de una para el mismo sibolo.

b

q0 q1a

ba

q0q0 b

a

Formalmente se define a un AFN por la quíntupla M=(Q,Σ,i,s,F) donde Q es un conjunto finito de estados, Σ 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, i es la función de transición, donde se puede apreciar que el contradominio de la función es el conjunto de potencias de Q, es decir que esta función devuelve conjuntos de estados en vez de un solo estado.

El AFN de la figura siguiente esta definido por Q=(q0,q1,q2,q3,q4), Σ={a ,b }, s=q0, F={q2,q3,q4} y i contiene las transiciones siguientes:I(q0,a)={q1,q4}, i(q1,a)={q1}, i(q4,b)={q4}, i(q0,b)={q3}, i(q1,b)={q2}.

Resumiendo, el AFN y todos sus elementos se muestran en la siguiente tabla por lo que podemos afirmar que esta table representa completamente al automata.

i a b→q0 {q1,q4} {q3}q1 {q1} {q2}q2 ∅ ∅q3 ∅ ∅q4 ∅ {q4}

2.4. Expresiones regulares

Podemos simplificar la especificación de un lenguaje regular utilizando nomenclatura abreviada, llamada expresión regular, de tal manera que el lenguaje unitario {a}, se denota simplemente como a.

Las operaciones de lenguajes regulares se denotan como: a U b, en vez de {a,b}; ab, en vez de {ab}; a* en vez de {a}* y a+ en vez de {a}+. El objetivo de esto es facilitar la lectura de los lenguajes regulares.

q2

Entonces podemos definir recursivamente lo que son las expresiones regulares :

∅y ε es un lenguaje regular. a es una expresión regular para toda a єΣ . Si r y s son dos expresiones regulares, entonces r U s, r * s y r* son

expresiones regulares. Ningun otra secuencia de simbolos es una expresión regular.

Ejemplo 1La expresión regular a*b U c representa a L=( {an }|n≥0 ∙ {b })U {c }

Teoremas sobre expresiones regulares

Sean r,s y t expresiones regulares sobre un alfabeto, entonces:1. r U s= sUr2. rU∅=∅Ur=r3. rUr=r4. (rUs)Ut=rU(sUt)5. rε=εr=r6. r∅=∅ r=∅7. (rs)t=r(st)8. r(sUt)=rsUrt9. (rUs)t=rtUst

2.7. Propiedades de lenguajes regulares 2.8. Propiedades de cierre 2.9. Unión, Concatenación, Cierre. Otras operaciones. 2.10. Algoritmos de decisión 2.11. Identificación de lenguajes no regulares 2.12. Otros tipos de autómatas2.13. Autómatas probabilísticas

3. LENGUAJES INDEPENDIENTES DEL CONTEXTO12horas3.1 Gramáticas independientes del contexto3.2. Reglas innecesarias, Símbolos inútiles, Reglas no generativas, Reglas unitarias.3.3. Formas normales3.4. Forma normal de Chomsky. 3.5. Forma normal de Greibach.3.6. Autómatas a pila3.7. Lenguajes independientes del contexto3.8. Propiedades de cierre, Homomorfismos, Cociente

4. MÁQUINAS DE TURING Y COMPUTABILIDAD12horas4.1. Máquinas de Turing4.2. Equivalencia entre máquinas secuenciales, Máquinas con alfabeto binario, Máquinas con cinta limitada en una dirección, Máquinas con dos cintas.4.3. MT para reconocer lenguajes4.4.. Lenguaje reconocido por una MT, MT para aceptar un lenguaje generado por una gramática de tipo 0.4.5. MT para computar funciones4.6. Funciones de un parámetro, Funciones de varios parámetros, Funciones complejas.4.7.. Máquina de Turing y Computación4.8. Tesis de Church/Turing4.9. Máquina de Turing Universal.4.10. Funciones computables.4.11. Enumerabilidad de conjuntos, Funciones no computables4.12. Decidibilidad.4.13. Funciones recursivas

4.14. Otros modelos de computación, Recursión en matemá

1.1Bibliografía