CONJUNTOSCONJUNTOS

El fundamento mas importante para el estudio de los lenguajes y autómatas es la Teorıa de Conjuntos. En efecto, siempre que hablemos de “formalizar” una nocion, estaremos diciendo en realidad “expresar en terminos de la Teorıa de Conjuntos”. La idea de un conjunto .

Las relaciones de inclusion entre conjuntos se acostumbran representar graficamente mediante

los llamados “diagramas de Venn”, que denotan mediante ´areas cerradas (por ejemplo elipses) los conjuntos. Por ejemplo, en la figura se ilustra la situacion donde un conjunto A es subconjunto de B, y B es subconjunto de C.

Sean A y B conjuntos. Se definen las siguientes operaciones con los conjuntos:

Union de conjuntos, denotada por A [ B, que contiene los elementos del conjunto A y tambien los del conjunto B, es decir, A [ B = {x|x 2 A o x 2 B}. Por ejemplo,

{1, 2, 3} [ {3, 4} = {1, 2, 3, 4}. La unión de conjuntos es conmutativa,

Interseccion de conjuntos, escrita A \ B, que contiene los elementos que pertenecen simultaneamente al conjunto A y al conjunto B, es decir, A \B = {x|x 2 A y x 2 B}.

Por ejemplo, {1, 2, 3} \ {3, 4} = {3}. La interseccion es conmutativa y asociativa.

Diferencia de conjuntos, A − B, que contiene los elementos de A que no estan en B, esto es, A − B = {x|x 2 A y x 62 B}. Por ejemplo, {1, 2, 3} − {3, 4} = {1, 2}. La resta o diferencia de conjuntos no siempre le “quita” elementos al primer conjunto; por ejemplo {1, 2, 3}−{4, 5} = {1, 2, 3}. La diferencia de conjuntos no es ni asociativa ni conmutativa

Complemento de un conjunto, es un caso particular de la diferencia, cuando el primer

conjunto es considerado como el “universo” que contiene todos los elementos posibles.

Sea U un universo, entonces el complemento del conjunto A, denotada por AC contiene

los elementos del universo que no están en A. Por ejemplo, si el universo son los

números naturales {1, 2, 3, . . .}, complemento de los números pares son los números

nones: {2, 4, 6, . . .}c = {1, 3, 5, . . .}. Claramente A [ Ac = U, para todo conjunto A.

Potencia de un conjunto A, denotada como 2A, contiene como elementos a todos los subconjuntos

de A, esto es, 2A = {x|x A}. En otras palabras, 2A es un conjunto de

conjuntos. Por ejemplo, 2{1,2,3} = {;, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}. Recu

´erdese que el conjunto vac´ıo siempre forma parte de todo conjunto potencia. La

notaci´on “2A” recuerda que el tama˜no del conjunto potencia de A es 2 elevado a la

potencia del tama˜no de A, esto es, |2A| = 2|A|.

Producto Cartesiano de dos conjuntos, A × B, es el conjunto de pares ordenados (a, b)

tales que a 2 A y b 2 B. Por ejemplo,{1, 2} × {3, 4, 5} = {(1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5)} El tamaño de un producto cartesiano A×B es |A| multiplicado por |B|, como se puede verificar en el ejemplo anterior. El producto cartesiano no es conmutativo, pues no es lo mismo un par (a, b) que uno (b, a), ni asociativo, pues no es lo mismo (a, (b, c)) que ((a, b), c).

Fundamentos MatemáticosFundamentos Matemáticos

Cadenas y LenguajesCadenas y LenguajesEl El producto cartesianoproducto cartesiano de dos de dos

conjuntos conjuntos AA y y BB consta de las parejas consta de las parejas ordenadas cuyo primer elemento ordenadas cuyo primer elemento está en está en AA y cuyo segundo elemento y cuyo segundo elemento está en está en BB. Usaremos la notación de . Usaremos la notación de yuxtaposiciónyuxtaposición para denotar al para denotar al producto cartesiano: producto cartesiano:

Monoide de CadenasMonoide de Cadenas

OPERACIÓN DE CONCATENACIONOPERACIÓN DE CONCATENACION

Creamos el diccionario de un alfabeto Creamos el diccionario de un alfabeto de la operación de de la operación de concatenaciónconcatenación: :

                   ,                    

Alfabeto, cadena de caracteres

Un alfabeto es un conjunto no vació de Un alfabeto es un conjunto no vació de símbolos. Así, el alfabeto del idioma símbolos. Así, el alfabeto del idioma español, E = {a, b, c, . . . , z}, es sólo uno español, E = {a, b, c, . . . , z}, es sólo uno de tantos alfabetos posibles. En general de tantos alfabetos posibles. En general utilizaremos la notación para representar utilizaremos la notación para representar un alfabeto.un alfabeto.

Con los símbolos de un alfabeto es posible Con los símbolos de un alfabeto es posible formar secuencias o formar secuencias o cadenas de caracterescadenas de caracteres, , tales como gegerte, sg536egdsge, r, etc. 4 tales como gegerte, sg536egdsge, r, etc. 4 Las cadenas de caracteres son llamadas Las cadenas de caracteres son llamadas también palabras.también palabras.

POTENCIA: de un conjunto A, denotada como 2A, contiene como elementos a todos los subconjuntos

de A, esto es, 2A = {x|x A}. En otras palabras, 2A es un conjunto de

conjuntos. Por ejemplo, 2{1,2,3} = {;, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}. Recu

´erdese que el conjunto vac´ıo siempre forma parte de todo conjunto potencia. La

notaci´on “2A” recuerda que el tama˜no del conjunto potencia de A es 2 elevado a la

potencia del tama˜no de A, esto es, |2A| = 2|A|.

GRAMATICASGRAMATICAS

SON SISTEMAS DE MANIPULACION SON SISTEMAS DE MANIPULACION SIMBOLICA QUE PERMITEN GENERAR SIMBOLICA QUE PERMITEN GENERAR CADENAS DE SIMBOLOS LLAMADAS CADENAS DE SIMBOLOS LLAMADAS POR ESTO BIEN FORMADAS, O BIEN POR ESTO BIEN FORMADAS, O BIEN RECONOCER CUANDO UNA CADENA RECONOCER CUANDO UNA CADENA DADA ESTA EN EFECTO BIEN DADA ESTA EN EFECTO BIEN FORMADA.FORMADA.

REGLAS DE TRANSFORMACIONREGLAS DE TRANSFORMACION

MAI : Modos Mecánico, Anti e MAI : Modos Mecánico, Anti e Inteligente (Zen) Inteligente (Zen)

Los caracteres griegos representan a Los caracteres griegos representan a palabras en el alfabeto . La primera regla palabras en el alfabeto . La primera regla dice que a toda palabra que termina con dice que a toda palabra que termina con ii puede añadírsele una puede añadírsele una aa, la segunda, que , la segunda, que toda palabra que comience con toda palabra que comience con mm puede puede repetir su ``resto'', la tercera, que repetir su ``resto'', la tercera, que cualquier cadena de tres cualquier cadena de tres ii-es consecutivas -es consecutivas puede cambiarse por una puede cambiarse por una aa, y, finalmente, , y, finalmente, que cualesquiera dos que cualesquiera dos aa-es consecutivas -es consecutivas pueden ser suprimidas. pueden ser suprimidas.

Ejemplo:Ejemplo:

Derivaciones en el sistema Derivaciones en el sistema MAIMAI. .

                                                                                                                      

                                

KENNINGS (Poesía antigua islandesa)KENNINGS (Poesía antigua islandesa) Este es un género de poesía islandesa de los Este es un género de poesía islandesa de los

siglos IX-XIII, construido mediante el siglos IX-XIII, construido mediante el reemplazo de frases sustantívales por otras reemplazo de frases sustantívales por otras equivalentes. equivalentes. Los kennings pueden ser Los kennings pueden ser bellas metáforas o irresolubles bellas metáforas o irresolubles acertijos. Ciertamente, esta poesía acertijos. Ciertamente, esta poesía posee dos tipos de encantos: Uno posee dos tipos de encantos: Uno sintáctico y otro semántico, y, por su sintáctico y otro semántico, y, por su naturaleza, ambos se mezclan naturaleza, ambos se mezclan indisolublemente.indisolublemente.

Ejemplos:Ejemplos:En un primer ejemplo, ilustramos la sustitución reiterada que se hace en En un primer ejemplo, ilustramos la sustitución reiterada que se hace en

los kennings, y en el segundo citamos un poema mucho más los kennings, y en el segundo citamos un poema mucho más acabado. acabado.

a)a) guerrero guerrero b)b) lanzador de espadaslanzador de espadasc)c) lanzador del fuego de la batallalanzador del fuego de la batallad)d) lanzador del fuego de la tormenta de arponeslanzador del fuego de la tormenta de arponese)e) lanzador del fuego de la tormenta de lunas de barcoslanzador del fuego de la tormenta de lunas de barcosf)f) lanzador del fuego de la tormenta de lunas de bridones de olas lanzador del fuego de la tormenta de lunas de bridones de olas .. .. ..Fonéticamente, en castellano es muy desagradable la repetición de la Fonéticamente, en castellano es muy desagradable la repetición de la

conjunción conjunción dede seguida de un artículo casi obligatorio. En los seguida de un artículo casi obligatorio. En los lenguajes nórdicos esto no aparece pues concatenando los vocablos, lenguajes nórdicos esto no aparece pues concatenando los vocablos, los sustantivos pueden realizar funciones de adjetivos, tal como los sustantivos pueden realizar funciones de adjetivos, tal como sucede en inglés. sucede en inglés.

ALGORITMO DE MARKOVALGORITMO DE MARKOV

Estos sistemas formalizan Estos sistemas formalizan procedimientos de cálculo. procedimientos de cálculo.

Los algoritmos de Markov son Los algoritmos de Markov son equivalentes a otros sistemas de equivalentes a otros sistemas de transformación como son las transformación como son las gramáticas formales gramáticas formales irrestrictasirrestrictas, las , las funciones recursivas y las máquinas funciones recursivas y las máquinas de Turing. de Turing.

Formalización de gramáticasFormalización de gramáticas

Sea Sea TT un conjunto de símbolos un conjunto de símbolos terminalesterminales y sea y sea VV un conjunto de un conjunto de símbolos símbolos variablesvariables. La unión de ellos, . La unión de ellos, , es un , es un alfabetoalfabeto de gramática. de gramática. AA* es * es el el diccionariodiccionario sobre sobre AA y consta de y consta de todas las palabras, de longitud finita, todas las palabras, de longitud finita, con símbolos en con símbolos en AA. . AA+ coincide con + coincide con AA*, salvo en que no posee a la *, salvo en que no posee a la palabra vacía, nil .palabra vacía, nil .

JERARQUIA DE CHOMSKYJERARQUIA DE CHOMSKY

En función de la forma de sus En función de la forma de sus producciones, se puede caracterizar qué producciones, se puede caracterizar qué tan compleja es una gramática formal. tan compleja es una gramática formal. Noam Chomsky mostró que esta Noam Chomsky mostró que esta caracterización clasifica jerárquicamente caracterización clasifica jerárquicamente a las gramáticas formales: Gramáticas a las gramáticas formales: Gramáticas en un nivel están incluidas en los en un nivel están incluidas en los siguientes niveles y la inclusión entre siguientes niveles y la inclusión entre niveles es propia. Se puede dar varios niveles es propia. Se puede dar varios refinamientos de la Jerarquía de refinamientos de la Jerarquía de ChomskyChomsky

Autómatas Autómatas

Los autómatas vienen a ser mecanismos Los autómatas vienen a ser mecanismos formales que ``realizan'' derivaciones en formales que ``realizan'' derivaciones en gramáticas formales. La manera en que las gramáticas formales. La manera en que las realizan es mediante la noción de realizan es mediante la noción de reconocimientoreconocimiento. Una palabra será generada . Una palabra será generada en una gramática si y sólo si la palabra hace en una gramática si y sólo si la palabra hace transitar al autómata correspondiente a sus transitar al autómata correspondiente a sus condiciones terminales. Por esto es que los condiciones terminales. Por esto es que los autómatas son autómatas son analizadores léxicosanalizadores léxicos (llamados en inglés ``(llamados en inglés ``parsersparsers'') de las '') de las gramáticas a que correspondengramáticas a que corresponden

Autómatas RegularesAutómatas Regulares

Estos son los autómatas finitos más Estos son los autómatas finitos más sencillos. Se construyen a partir de un sencillos. Se construyen a partir de un conjunto de conjunto de estadosestados QQ y de un conjunto y de un conjunto de de símbolos de entradasímbolos de entrada TT. Su . Su funcionamiento queda determinado por funcionamiento queda determinado por una una función de transición t: q x T--función de transición t: q x T-- Q . Q .

Si Si tt((qq,,ss)=)=pp esto se interpreta como que esto se interpreta como que el autómata transita del estado el autómata transita del estado qq al al estado estado pp cuando arriba el símbolo cuando arriba el símbolo ss. En . En todo autómata finito se cuenta con un todo autómata finito se cuenta con un estado inicial q0 € Q y un conjunto de estado inicial q0 € Q y un conjunto de estados finales F C Q.estados finales F C Q.

Autómatas de PilaAutómatas de PilaEstos autómatas finitos cuentan con un Estos autómatas finitos cuentan con un dispositivo de memoria muy elemental, del dispositivo de memoria muy elemental, del tipo tipo pilapila, el cual es un almacenamiento lineal , el cual es un almacenamiento lineal que funciona bajo el principio PEUS: que funciona bajo el principio PEUS: Primero Primero en Entrar, Ultimo en Saliren Entrar, Ultimo en Salir..La función de La función de transicióntransición es de la forma t: Q x es de la forma t: Q x T x V T x V → Q x V→ Q x V**, donde la relación , donde la relación t(q,a,v)=(p,v) se interpreta: ``Si se está en t(q,a,v)=(p,v) se interpreta: ``Si se está en el estado el estado qq, arriba el símbolo , arriba el símbolo aa y en el tope y en el tope de la pila está el símbolo de la pila está el símbolo bb entonces se pasa entonces se pasa al estado al estado pp y se empila la palabra y se empila la palabra vv ''. ''. Un autómata de pila reconoce a una palabra Un autómata de pila reconoce a una palabra si, tras haberla leído, termina con su pila si, tras haberla leído, termina con su pila vacíavacía

Autómatas de PilaAutómatas de PilaConsideremos el autómata de pila cuyas Consideremos el autómata de pila cuyas componentes son las siguientes:componentes son las siguientes:

Q={Seguir, Éxito, Fracaso}Q={Seguir, Éxito, Fracaso} : estados,: estados,T={a,b,c}:símbolos de entrada,V={A,C}T={a,b,c}:símbolos de entrada,V={A,C}

:símbolos de Pila,:símbolos de Pila,qq00=Seguir=Seguir :símbolo inicial,:símbolo inicial,Y cuya función de transición actúa como sigue:Y cuya función de transición actúa como sigue:

(seguir,a,y)(seguir,a,y)→(Seguir,Ay) empila paréntesis →(Seguir,Ay) empila paréntesis que abrenque abren(seguir,c,A)→(seguir,nil) suprime paréntesis (seguir,c,A)→(seguir,nil) suprime paréntesis empatadosempatados

t:t: (seguir,c,nil)→(fracaso,C) no hay equilibrio,(seguir,c,nil)→(fracaso,C) no hay equilibrio,(seguir,b,A)→(fracaso,A) no hay equilibrio,(seguir,b,A)→(fracaso,A) no hay equilibrio,(seguir,b,nil)→(Éxito,nil) equilibrio verificado(seguir,b,nil)→(Éxito,nil) equilibrio verificado

Autómatas finitos

El término maquina evoca algo hecho El término maquina evoca algo hecho en metal, usualmente ruidoso y en metal, usualmente ruidoso y grasoso, que ejecuta tareas grasoso, que ejecuta tareas repetitivas que requieren de mucha repetitivas que requieren de mucha fuerza o velocidad o precisión. fuerza o velocidad o precisión. Ejemplos de estas máquinas son las Ejemplos de estas máquinas son las embotelladoras automáticas de embotelladoras automáticas de refrescos.refrescos.

Autómatas LinealesAutómatas Lineales

Los Los autómatas linealesautómatas lineales son autómatas son autómatas de pila deterministas que a lo largo de de pila deterministas que a lo largo de su computación sólo hacen un ``cambio su computación sólo hacen un ``cambio de turno''. A grandes rasgos, esto de turno''. A grandes rasgos, esto significa que toda computación consiste significa que toda computación consiste de un procedimiento de empilar de un procedimiento de empilar consecutivamente para después pasar a consecutivamente para después pasar a desempilar.desempilar.

Relaciones De OrdenRelaciones De Orden

ORDEN DE PREFIJOORDEN DE PREFIJOPrimeramente presentamos condiciones Primeramente presentamos condiciones

necesarias y suficientes para comparar necesarias y suficientes para comparar cadenas y subcadenas. cadenas y subcadenas.

ORDEN LEXICOGRAFICOORDEN LEXICOGRAFICOSea Sea ∑∑*un alfabeto dotado de un *un alfabeto dotado de un

orden”orden”≤”≤” ejemplo, para el alfabeto ejemplo, para el alfabeto ASCII consideramos el orden usual. ASCII consideramos el orden usual. Extendemos el orden “Extendemos el orden “≤” de ∑ a un ≤” de ∑ a un orden de ∑orden de ∑*.*.

HomomorfismosHomomorfismos

Sean (Sean (SS1,*1,1,*1,uu1) y (1) y (SS2,*2,2,*2,uu2) dos monoides con 2) dos monoides con operaciones respectivas *1 y *2 y unidades operaciones respectivas *1 y *2 y unidades uu1 y 1 y uu2. Una función es un 2. Una función es un homomorfismohomomorfismo si si

En otras palabras, un homomorfismo es una En otras palabras, un homomorfismo es una correspondencia entre monoides que preserva las correspondencia entre monoides que preserva las operaciones. operaciones.

Relaciones de EquivalenciaRelaciones de Equivalencia

En un conjunto En un conjunto AA, una , una relación de relación de equivalenciaequivalencia RR es un subconjunto es un subconjunto tal que es tal que es

reflexiva: , ,reflexiva: , , simétrica: simétrica:

,y ,y

transitiva: transitiva: . .

Lenguajes

La noción más primitiva es la de La noción más primitiva es la de símbolo, que es simplemente una símbolo, que es simplemente una representación distinguible de representación distinguible de cualquier información. Los símbolos cualquier información. Los símbolos pueden ser cualesquiera, como w, 9, pueden ser cualesquiera, como w, 9, #, etc.,pero nosotros vamos a utilizar #, etc.,pero nosotros vamos a utilizar las letras a,b,c, etc. Un símbolo es las letras a,b,c, etc. Un símbolo es una entidad indivisible.una entidad indivisible.

Lenguajes, operaciones con lenguajes

Un lenguaje es simplemente un Un lenguaje es simplemente un conjunto de palabras. Así, conjunto de palabras. Así, {abracadabra} es un lenguaje (de {abracadabra} es un lenguaje (de una sola palabra), {ali, baba, y, sus, una sola palabra), {ali, baba, y, sus, cuarenta, ladrones} es otro, es otro, cuarenta, ladrones} es otro, es otro, etc.etc.

GRAMATICAS FORMALESGRAMATICAS FORMALES

Una gramática es una estructura G = Una gramática es una estructura G = (V, T, P So,) donde las siguientes letras (V, T, P So,) donde las siguientes letras

representan:representan:

““V: Símbolos Variables”V: Símbolos Variables”

““T: Símbolos Terminales”T: Símbolos Terminales”

““P: Producciones o reglas sintácticas”P: Producciones o reglas sintácticas”

““So: Símbolo Inicial”So: Símbolo Inicial”

PROPOSICIONES CORRECTAMENTE PROPOSICIONES CORRECTAMENTE FORMADASFORMADAS

Las proposiciones se construyen a partir de Las proposiciones se construyen a partir de un conjunto de variables proposicionales que un conjunto de variables proposicionales que siguen un conjunto de reglas gramaticales:siguen un conjunto de reglas gramaticales:

Una variable proposicional es una proposiciónUna variable proposicional es una proposición La negación de una proposición es una La negación de una proposición es una

proposición tambiénproposición también La conjunción, la disyunción, la implicación y La conjunción, la disyunción, la implicación y

la equivalencia de dos proposiciones es la equivalencia de dos proposiciones es también una proposicióntambién una proposición

Las proposiciones solo se obtiene mediante la Las proposiciones solo se obtiene mediante la aplicación sucesiva de las reglas anterioresaplicación sucesiva de las reglas anteriores

Para describir esta construcción Para describir esta construcción mediante una grámatica formal, mediante una grámatica formal, podemos considerar como un podemos considerar como un conjunto de símbolos terminales a conjunto de símbolos terminales a conjunto unión de los siguientes :conjunto unión de los siguientes :

Tabla de proridades de los Tabla de proridades de los conectivos:conectivos:

La prioridad de los conectivos da de La prioridad de los conectivos da de izquierda a derechaizquierda a derecha

TERCETAS DE IGUAL LONGITUDTERCETAS DE IGUAL LONGITUD

En este lenguaje En este lenguaje consta de tres consta de tres bloques bloques consecutivos a’s, consecutivos a’s, b’s y c’s de b’s y c’s de igual igual longitudlongitud, sus reglas , sus reglas de producción son de producción son las siguientes:las siguientes:

GRAMATICA:GRAMATICA:

Toda palabra generada en ella tiene un Toda palabra generada en ella tiene un longitud de múltiplos de 3longitud de múltiplos de 3

Toda la palabra generada es de la forma Toda la palabra generada es de la forma aakk,b,bkk y c y ck k para algún k para algún k ≥ 0≥ 0

En general la grámatica utlizada es :En general la grámatica utlizada es :

L(gramática) = LL(gramática) = L33

PAREJAS DE IGUAL LONGITUDPAREJAS DE IGUAL LONGITUD

Esta grámatica es Esta grámatica es paracida a la paracida a la gramática de gramática de tercetas de igual tercetas de igual longitud solo que longitud solo que se suprime el se suprime el último bloque c’s. último bloque c’s. Sus reglas de Sus reglas de producción son las producción son las siguientes:siguientes:

PALABRAS DOBLESPALABRAS DOBLES

En este lenguaje En este lenguaje consta de la consta de la palabras formadas palabras formadas por la repetición de por la repetición de una partícula en el una partícula en el alfabeto {0,1}, su alfabeto {0,1}, su gramática es:gramática es:

De las reglas de producción se podemos De las reglas de producción se podemos considerar los siguientes símbolos:considerar los siguientes símbolos:

““S: Símbolo Inicial”S: Símbolo Inicial” ““A: Delimitador derecho del primer A: Delimitador derecho del primer

bloque”bloque” ““B: ‘cursor’ para seguir añadiendo B: ‘cursor’ para seguir añadiendo símbolos en los bloques generados”símbolos en los bloques generados”

““C: Delimitador derecho del segundo C: Delimitador derecho del segundo bloque”bloque”

““D: Recordatorio de que sea generado un D: Recordatorio de que sea generado un 0”0”

““E: Recordatorio que se ha generado un 1”E: Recordatorio que se ha generado un 1”

ELEVACION AL CUADRADOELEVACION AL CUADRADO

Esta gramática se construye a partir Esta gramática se construye a partir de las cadenas de 1’s cuya longitud de las cadenas de 1’s cuya longitud es el cuadrado de un número es el cuadrado de un número positivo. Ya que para todo nodo n, positivo. Ya que para todo nodo n, (n+1)(n+1)22, y al incio, 1, y al incio, 122 = 1, la = 1, la gramática, una vez que genere una gramática, una vez que genere una cadena de longitud ncadena de longitud n22 ha de ha de concatenar con una de longitud n y concatenar con una de longitud n y otra de longitud n + 1.otra de longitud n + 1.

Producciondes de Producciondes de elevación al elevación al cuadrado:cuadrado: