MINIMIZACIN DE ESTADOS EN UN DE AF

Lenguaje y Autmatas
29/03/2013 Ing. Sistemas Computacionales Angel Fuertes Gomez

INTRODUCCIN Recordatorio: Conjunto distinguible, CD, de palabras con respecto a un L, es un conjunto S * tal que cada par de palabras del conjunto son distinguibles entre s con respecto a L. Definicin: Conjunto distinguible mximo, CDM, es un CD tal que, cualquier otra palabra x * x S es indistinguible de, al menos, una z S con respecto a L. Es evidente que si a un CDM se le aade una palabra nueva, deja de ser un conjunto distinguible (CD). Recordatorio: Teorema de la distinguibilidad: "Si tenemos n palabras de * que son distinguibles entre s dos a dos respecto de L, el autmata que reconoce L tiene, al menos, n estados". Viceversamente, si tenemos un AF con n estados, ese AF reconoce un L tal que del mismo no se pueden obtener ms de n cadenas distinguibles entre s 2 a 2 respecto de L; es decir, no existe CD que tenga ms de n cadenas. Por tanto, si tenemos un CDM con n palabras, necesitamos, al menos, n estados para reconocer L. Luego el AF mnimo (AFM) para reconocer L ha de tener n estados. Con menos estados no se pueden diferenciar entre s las n palabras de un CDM. Partiremos de esa propiedad para deducir el AFM, que es nico. Pero el problema de la minimizacin es que se parte de un AF no mnimo, no de un CDM. Es decir, hay muchos AFs distintos, pero equivalentes. Hemos de ver las relaciones entre ellos. De esas relaciones deduciremos el algoritmo de minimizacin. CLASES DE EQUIVALENCIA La indistinguibilidad es una relacin de equivalencia. En efecto: Para x , y * se denota x IL y. Cumple las propiedades: 1) x IL x (reflexiva). Toda palabra es indistinguible de s misma con respecto a L. 2) Si x IL y , tambin se verifica y I L x (simtrica). La relacin de indistinguibilidad no tiene orden. 3) Si x IL y y IL w, se cumple x IL w (transitiva). En efecto para cualquier cola z * , x z L ( o L ) y z L (o L). Y tambin y z L (o L) w z L (o L). Pero si una cola z lleva a que y z L (o L), como se verifica por hiptesis y IL w, esa misma cola z lleva a que w z L (o L). Luego una cola z que hace que x z L (o L) w z L (o L). O sea se verifica x IL w, c.q.d. El monoide libre queda dividido en clases de equivalencia: [x1], [x2], ..... Lo que significa que cualesquiera dos palabras escogidas de diferentes clases son distinguibles entre s, ya que si no lo fueran estaran en la misma clase; o sea no hay palabra que pertenezca a la vez a dos clases distintas. Lo que es lo mismo que decir: Lema: "Un CD es M cuando est formado por una palabra de cada clase". Evidentemente, un CD est formado por cadenas que pertenecen cada una a una clase distinta de las dems. Ser mximo cuando hay cadenas de todas las clases. Por tanto "si L es regular, todo CDM tendr el mismo nmero de cadenas", obviamente el nmero de clases de equivalencia.

Mtodo para obtener las clases Se debe empezar encontrando algn CD de dos palabras, siendo stas lo ms cortas posible. Partiendo del mismo se debe intentar ampliar el nmero de palabras del CD, hasta que no se pueda incluir ninguna palabra ms. Entonces se ha llegado a un CDM. La justificacin de no poder incluir palabra nueva alguna lleva directamente a la definicin de las clases de equivalencia. Ejemplo: L: (a + b)* a. Es fcil comprobar que un CD es { , a}, as como que es mximo. Con respecto a este L, (a + b)* tiene dos clases de equivalencia: [a] = L y [] = * - L. Cualquier pareja de valores del conjunto L X [] es un CD, que es, obviamente, CDM.

RELACIN ENTRE CLASES Y ESTADOS

Antes de relacionar las clases de equivalencia con el autmata que reconoce al L con respecto al cual las cadenas son indistinguibles, es interesante saber algo sobre la particin en clases de equivalencia. Dado L, cmo se hara la particin de (a + b)*?. El problema general es complicado, pero podemos preguntarnos cosas como: las palabras x L son indistinguibles entre s respecto de L?.La respuesta es que no necesariamente tienen que serlo; no tienen por qu pertenecer a una misma clase. P. ej., dado el L de expresin regular (a a) * (a b)*, las palabras aa y ab son distinguibles con respecto a L. En efecto dada la cola z = a a, resulta que a a a a L mientras que a b a a L. Una reflexin sobre este caso nos lleva a dos clases diferentes: [ ] y [a b] siendo [] = [, a a, a a a a, ......] = { x x {a a}* } y [a b] = { x x {a a}* {a b}+ }, x es cualquier palabra de la clase [] seguida de, como mnimo, una cadena a b`. Es fcil comprobarlo: As: a a` y a a a a` son indistinguibles, ya que para una cola z [], las dos palabras resultantes [], mientras que para cualquier otra cola z [], se pueden presentar dos casos: O bien z {a b}+ o bien z {a b}+ . Es fcil comprobar que en el primer caso las dos resultantes L, mientras que en el segundo ambas L. Todas las palabras de nmero par de as son indistinguibles entre s con respecto a L. Igual pasa con a a a b` y a b`, p. ej. Para z {a b}* ambas resultantes [a b] y para cualquier z {a b}* ambas [a b]. Pero si escogemos una palabra [] y otra [a b] ambas son distinguibles. P.e. a a` y a b`, como ya vimos. Ya tenemos un CD de dos palabras. Podemos aadir palabras nuevas; pero no podemos pasar de cinco en total. Las nuevas clases, tres, corresponden a las palabras que L: [a] = (a a)* a: Palabras con nmero impar de as. [a b a] = (a a)* (a b)+ a = [a] {b a}+ [a a b] = ( (a a)* b + (a a)* (a b)+ b + (a a)* (a b)+ a a) (a + b)*: El resto de palabras. AF mnimo Supongamos que tenemos un AF que reconoce L y que tiene el menor nmero posible de estados. Definicin : Lq = conjunto de x * que se aceptan en el estado q Q, o sea Lq = {x * (q0 , x ) = q} Es evidente que todas las palabras que pertenecen a un mismo Lq son indistinguibles entre s respecto a Lq. Pero tambin son indistinguibles entre s respecto a L, puesto que, a partir del estado q, cualquier cola z recorrer un nico itinerario. Tambin es incuestionable que L q Lr para q r y q, r Q, as como que Lq Lr = . Adems, cuando el autmata es mnimo, y slo en ese caso, el autmata tiene un estado por cada clase indistinguible. Vemoslo. Cuando el autmata no es mnimo, puede tener estados distintos, p. ej. q y r ,

reconociendo Lq y Lr respectivamente, pero las palabras de Lq y Lr pueden ser tambin indistinguibles entre s. P.e. el AF reconoce a* y es mnimo, pero tambin reconoce ese a, b a lenguaje el AF 1 a 2 b b 3 a, b siendo L1 = {} y L2 = {a}+. Se ve que L1 L2 = , pero se cumple IL x para todo x {a}+. a b Es decir cuando el autmata no es mnimo, es porque hay estados distintos en l a los que conducen palabras distintas que son indistinguibles entre s. En cambio si el AF es mnimo, esa indistinguibilidad entre palabras que llevan a diferentes estados deja de producirse. As pues en un AFM, si dos cadenas x, y * son indistinguibles respecto de L, o sea, cumplen la relacin x IL y, es porque llevan al mismo estado : * (q0, x) = *(q0, y) = q y pertenecen a la misma clase de equivalencia. O, lo que es igual, dos palabras pertenecen a la misma clase de equivalencia cuando son equivalentes respecto a la relacin IL. As pues, "los conjuntos Lq son las clases de equivalencia cuando el AF es M". Se pueden identificar, pues, los estados del AFM con las clases de equivalencia [x 1], [x2], ..... As el AFM que reconoce el L de las palabras que terminan en a tiene dos estados; pero hay muchos otros, infinitos, autmatas equivalentes con ms de dos estados. Solamente en el mnimo se verifica L1 = [] y L2 = [a]. Ya sabemos el nmero de estados del AFM reconocedor del L regular y la caracterizacin de cada estado como aceptador de las palabras de una clase de equivalencia, as como el estado inicial y el conjunto de estados de aceptacin. Necesitamos conocer ahora la funcin de transicin. La siguiente propiedad, exclusivamente lingstica, nos proporciona las bases para lograrla. Propiedad: "Las clases de equivalencia son consistentes con respecto a la concatenacin por la derecha con las letras del alfabeto". O sea, la operacin de concatenacin no depende del representante elegido de la clase. La funcin de transicin, para estar bien definida, a [x] [xa] ([x], a) = [xa]

necesita del cumplimiento de esa propiedad. Es decir, si x IL y, entonces para cualquier a , se ha de cumplir x a IL y a. En trminos de clases de equivalencia: si [x] = [y] entonces [x a] = [y a]. Se dice que IL es invariante por la derecha con respecto a la concatenacin. Es fcil probarlo. Si x IL y, z * se verifica que x z y z L (o L). Sea z = a z (ya que se cumple para cualquier z). Entonces se cumple que x a z e y a z(siendo z cualquier palabra) tambin pertenecen ambas a L (o L). O sea [x a] = [y a]. De esta propiedad se obtiene directamente la funcin de transicin.

Teorema: " El AF mnimo que reconoce L es ML = < QL, , q0, , A >, siendo QL el conjunto finito de clases de equivalencia de * respecto de L, q0 = [], A = {q QL q L } y : Q X Q tal que ([x], a ) = [x a] para todo [x] QL y todo a ". Esta definicin de la funcin de transicin es correcta, de acuerdo con la propiedad anterior. Para demostrar que esa definicin de la funcin de transicin es consistente con la definicin de aceptacin de toda palabra de L y de rechazo de toda palabra de L, hemos de ver que ML acepta una palabra x slo si x L y que ML no tiene ms estados que el nmero de clases de equivalencia (esto ltimo es as por definicin). En efecto: Si x L, para ser aceptada por ML se ha de verificar: (* ([], x ) = [x] ) ( [x] L ). Para demostrarlo ha de demostrarse que, en general, es * ([x], y) = [x y] para cualesquiera [x] QL , y * Demostracin por induccin: - Base: *([x], ) = [x] = [x ]. Si no se lee nada, se contina en el estado [x]. - Hiptesis : * ([x], y ) = [x y] para |y| = k, y * - Tesis: * ([x], y a )= [x y a] para a En efecto * ([x], y a) = (* ([x], y), a), y por la hiptesis, es = ([x y], a). Pero por construccin de la funcin. de transicin es = [x y a], c. q. d.. Por tanto, en particular para el estado inicial, se verifica: * ([], x) = [x]. Para ver que slo se acepta x L si [x] L , debe ocurrir que * ([], x) ha de pertenecer a A para todo x L. Pero es fcil ver que [x] L es igual que decir x L Desde luego, si x L, es claro que [x] L . Y si hay otra cadena y [x] es x IL y; por tanto si x L, tambin y L. Entonces ML acepta x siempre que x L. Y no se aceptan palabras que L. Toda x L es distinguible de cualquier y L. Consiguientemente pertenece a una clase de indistinguibilidad [x] tal que [x] L = . Ahora bien * ([], x) = [x] y el estado [x] A. Luego toda palabra que L es rechazada. As pues ML acepta x s.s.s. x L. Ejemplo1: (a + b) * a Dos clases: L1 = [] , L = [ a] Dos estados: 1 y 2. Estado inicial: 1. Propiedad de concatenacin: [ ] a = [a]; [] b = [ ]; [a] a = [a]; [a] b = []. De ella se deduce directamente la funcin de transicin. Ejemplo2: L = {x {0,1}* x termina en 10} Sean x1 = , x2 = 1 y x3 = 10 Veamos que {x1, x2, x3} es un CD (es fcil probarlo). Veamos que, adems, es un CDM.. En efecto para cualquier x * hay algn miembro (x1, x2, x3) del CD que es indistinguible de x respecto de L. Para verlo han de tenerse en cuenta todas las posibilidades de x, que son tres, independientemente del prefijo: a) Termina en 10 (indistinguible de x3); b) Termina en 1 (indistinguible de x2) y c) Es , es 0` o termina en 00; o sea no termina en 1 ni en 10 (indistinguible de x1). Entonces las clases de equivalencia son [x1], [x2] y [x3]: [x1] = {x no termina en 1 en 10}; [x2] = { x termina en 1}; [x3] = { x termina en 10}. El estado inicial es q0 = [x1] y el conjunto de estados de aceptacin es A = {[x3]}. La funcin de transicin es:

 ([x1], 0) = [x10] = [x1]; ([x1], 1) = [x11] = [x2]; ([x2], 0) = [x20] = [x3]; ([x2], 1) = [x21] = [x2]; ([x3], 0) = [x30] = [x1]; ([x3], 1) = [x31] = [x2]. El grafo del AFM es: 0 1 1 0 X x1 x2 3 1 0 RELACIONES ENTRE LOS RECONOCEDORES DE UN L REGULAR No es fcil, dado L, encontrar un CDM, o sea, lo que es prcticamente igual, las clases de equivalencia que induce la relacin de indistinguibilidad con respecto a L. Por otra parte el problema de la minimizacin es que no se parte de las clases sino de un autmata, ya construido, que reconoce L. Entonces la primera cuestin es: es ese AF mnimo?. Y, si no lo es, cmo obtener, a partir de l, el AFM?. Para responder a esas preguntas vamos a ver las relaciones estructurales que existen entre los diferentes AF que reconocen L. Hemos visto que el AFM induce una particin de * en n clases, siendo n el n de estados. Dado un estado, q, del AFM, Lq es una clase de equivalencia. Si M es un autmata no mnimo, ya sabemos que, para cualquier q Q, Lq es un conjunto de palabras indistinguibles entre s con respecto a L; adems si q, r Q y q r, es Lq Lr = ; luego M induce una particin en *. Ahora la pregunta es: Qu relacin hay entre las diferentes particiones que los distintos autmatas reconocedores de L inducen en *?. Pensemos en un M no mnimo. Si q Q, Lq es, o bien una clase de equivalencia, o no. En cualquier caso, todas las palabras de Lq pertenecen a una misma clase de equivalencia, puesto que son indistinguibles entre s con respecto a L. Y, por la propiedad de las particiones (si q r , Lq Lr = , y si [x] [y] es [x] [y] = ), se deduce que Lq tiene interseccin no nula con slo una clase de equivalencia, y slo una. Si consideramos una clase de equivalencia, digamos [x], si una palabra x [x], tambin x Lq para algn estado q. Pero toda palabra de Lq pertenece a la clase [x] o sea Lq [x], porque Lq posee interseccin no nula con slo esa clase. Por tanto, una clase de equivalencia es la unin de varios, como mnimo uno, Lq. Veamos el ejemplo2: L= {x * x termina en 10`} Comparemos un autmata reconocedor no mnimo y el mnimo.

0 0 2 0 4 0 0 1 1 0 c

a 0

b 1

1 1 0 3 1 7 7 0 1

5 0 L6 = L = LC 6 1

L1 = {}

L2 = {0}

L3 = {1} L5 = * {01}

La Lb Lc La = L1 L2 L4 Lb = L3 L5 L7 Lc = L6 = L

L4 = {0,1}* {00} L6 = * {10}

L7 = * {11}

ALGORITMO DE MINIMIZACIN As pues, si un M es mnimo, cada clase de equivalencia con respecto a IL corresponde a un solo estado. Si no es mnimo, hay distintos estados (p, q corresponden a Lp y Lq) de forma que Lp y Lq son subconjuntos de la misma clase de equivalencia. De esta observacin se deduce un algoritmo para minimizacin. Cmo mezclar los estados para deducir de varios de ellos un solo estado del AFM?. Hemos de identificar aquellos pares de estados p, q tales que Lp y Lq son subconjuntos de la misma clase de equivalencia, o bien el problema inverso: identificar aquellas parejas de estados (p, q) tales que ambos pertenecen a clases diferentes. Las parejas que queden sin marcar son las que corresponden a estados que pueden unirse de manera que resulten los estados del AFM. Para encontrar las parejas de estados que pertenecen a clases de indistinguibilidad diferentes hemos de apoyarnos en la estructura del autmata (los estados y la funcin de transicin), las relaciones entre las clases de indistinguibilidad y una observacin sobre la aceptacin. Esta ltima consiste en que la aceptacin por el M de las palabras de L es una relacin de equivalencia en el conjunto de las clases de indistinguibilidad que induce en este ltimo una particin en dos clases: las que corresponden a estados de no aceptacin (del AFM) y las que corresponden a estados de rechazo. Por tanto si el M es no mnimo, un L q que corresponda a un estado q de rechazo pertenecer a una clase Lq [x] que en el AFM ser un estado de rechazo; y si Lq corresponde a un q de aceptacin, entonces si Lq [x], [x] es un

estado de aceptacin en el AFM. Esta ltima observacin nos permite arrancar para marcar las parejas de estados (p, q), p, q M, que pertenecen a clases diferentes. En efecto, en M si p q y p A q A, o bien p A q A, entonces p y q pertenecen a clases de equivalencia diferentes, una correspondiente a algn estado de aceptacin del AFM y la otra a uno de rechazo. Notacin : p q si Lp y Lq son subconjuntos de la misma clase de equivalencia. p # q si pertenecen a clases diferentes. El algoritmo para encontrar las parejas (p,q) tales que p # q se basa en las siguientes observaciones: 1: Si solo uno de los dos estados (o bien p o bien q) A, entonces p # q (puesto que si x L y L, o viceversa, es x de una clase e y de otra). 2: Si * (r, w) = p * (s, w) = q p # q, entonces r # s. En efecto supongamos x Lr, y Ls; entonces x w Lp y w Lq. Pero si es x w distinguible de y w, ha de ser porque x es distinguible de y, o sea, r # s, c. q. d. 3: Si r # s, hay al menos una cadena z tal que si x Lr y Ls, una cadena x z (o la otra y z `) L, y la otra y z (o la otra x z ) L (o bien *(r, z) A, o bien *(s, z) A, pero solo una). De estas observaciones se deducen las parejas de estados que no se pueden mezclar. Algoritmo MP (Marcar Parejas) en el autmata M. Sobre la lista (p, q) de parejas de estados: 1: Marcar las parejas que tienen slo un elemento (bien p, bien q) en A. 2: Marcar las parejas (r, s) tales que (r, a) = p (para algn a ) (s, a) = q (p, q) est previamente marcada. 3: Si en el paso 2 se termina sin marcar ninguna nueva pareja, entonces FIN. Si se marca alguna nueva pareja, volver al paso 2. El Algoritmo es correcto, completo(por la observacin 3) y finito. En efecto, toda pareja (p, q) ser marcada si p # q(para ello es preciso que en M se haya prescindido previamente de los estados no alcanzables). Apliquemos el Algoritmo al ejemplo { x termina 10`}: En dos pasos se termina: En el 1 () es (p A q A) (p A q A). En el 2 se aplica la observacin 2 de forma exhaustiva para las letras del alfabeto. P. ej. la pareja (2, 5) con respecto a la (4, 6) verifica: (2, 0) = 4 (5, 0) = 6 (4, 6) est previamente marcada. Consiguientemente, 2 # 5. Y as para todas las parejas posibles. El resultado es la tabla siguiente:

2 3 4 5 6 7 < < < < < < < < <

MP

A partir de las parejas marcadas como resultado del Algoritmo MP, Cmo llegar a la particin en las clases de equivalencia?. Primero vamos a construir el conjunto Q 1 de estados de M1 (AFM). Nos basamos en las siguientes observaciones: a) Si para un estado p ocurre que todas las parejas (p, q), para todo q Q (excepto p = q) verifican p # q, entonces p corresponde exactamente a una clase de equivalencia. Eso ocurre en el ejemplo para el estado 6. Obsrvese la tabla. Pero si hay al menos un estado q tal que p q, entonces todos los estados q en los que eso ocurra pueden mezclarse con p para formar un nico estado del AFM (una clase de equivalencia). b) Todos los estados de M que se pueden mezclar para formar un nico estado del AFM son estados de aceptacin, o bien ninguno lo es, de forma que el estado resultante de la mezcla es un estado de aceptacin en el primer caso, o bien no lo es, en el segundo caso. En el ejemplo (7, 3) y (7, 5) forman un estado de rechazo, as como (4, 1) y (4, 2). Nos queda: Cmo llegar en el AFM a 1 (q, a )? Vamos a construir la funcin de transicin. Si en M es (p, a) = q (r, a) = s y q y s se han mezclado en M1 en un nico estado t, la cuestin es p r?. Puede ser SI o NO. En cualquier caso, no hay problema para construir la funcin de transicin. Si SI, estn mezclados p y r en un estado u y es 1 (u, a) = t. Si NO, es 1 (p, a) = t 1 (r, a) = t. Para cada estado q QM (estados del AFM), hay que calcular 1 (q, a) para a . Conocemos los estados, p, de los que procede cada estado, q, del AFM: q = {p p Q} (Q conjunto de estados del AF no Mnimo). Construimos 1(q, a) a partir de (p, a): 1 (q, a) = (p, a) es un conjunto de estados que pertenecen a pq la misma clase de indistinguibilidad. As, de los dos autmatas equivalentes del ejemplo: 1 (a, 0) = (1, 0) (2, 0) (4, 0) = 2 4 4 = a 1 (a, 1) = (1, 1) (2, 1) (4, 1) = 3 5 5 = b 1 (b, 0) = (3, 0) (5, 0) (7, 0) = 6 6 6 = c 1 (b, 1) = (3, 1) (5, 1) (7, 1) = 7 7 7 = b 1 (c, 0) = (6, 0) = 4 = a 1 (c, 1 = (6, 1) = 5 = b M1 0 1 a 0 Es fcil probar que L (M) = L ( M1 ) y que M1 tiene el mnimo nmero de estados posible. El resultado del algoritmo de minimizacin es un homomorfismo: b 1 1 0 c

f: Q Q1

con f ( q0) = q1 y cumpliendo 1 (f(q), a) = f ( (q, a)) f f

q q a M a f (q, a) (q,a) f

f (q) a M1 1 (f(q), a)

f(q) = f(q) si Lq y Lq corresponden a la misma clase con respecto a la relacin IL. En ese caso es f((q, a) = f((q, a)). Y tambin f((q, x)= f((q, x)), x *. En general es fcil verificar, por induccin, que *1 (f (q), x) = f (* (q, x)) Aplicando esa propiedad es fcil ver que para x, si x es aceptada por M, x es aceptada por M1 y si x no es aceptada por M, tampoco lo es por M1. Por otra parte, el algoritmo mezcla todos los estados que corresponden a la misma clase de equivalencia. Los estados resultantes son as las clases de equivalencia y, por consiguiente, M1 es mnimo, como a continuacin vamos a ver. Teorema: "Si M1 y M2 son autmatas finitos mnimos que reconocen el mismo L, son isomorfos". Es fcil mostrarlo por la construccin implicada en el algoritmo de minimizacin: 1 (f (q), a) = f ( (q, a)) - homomorfismo En particular, si los dos son mnimos, f es un isomorfismo. En efecto, supongamos que M1 (mnimo) proviene del AF M1 (no mnimo) y M2 (mnimo) proviene del AF M2 (no mnimo y M1). Lo evidente es que M1 y M2 tienen el mismo nmero de estados (el nmero de clases de equivalencia). Llamando 1, 2, 1, 2 las diferentes funciones de transicin, se ha de verificar: f1 (1 (q, a)) = 1 (f1 (q), a), q Q1 f2 (2 (q, a)) = 2 (f2 (q), a), q Q2 Pero f1 y f2 son funciones inyectivas (n en 1) en donde varan los estados origen (n) pero no los estados de llegada (1- clase de indistinguibilidad). Por consiguiente los autmatas mnimos son isomorfos. Es decir, existe una funcin biunvoca, llamemos g: [x] [y] siendo [x] Q1, [y] Q2 (mnimos), tal que, si g ([x]) = [y], se verifica: g [x] a [xa] g Si (1 ([x], a) = [xa]) (2 ([y], a = [y a ]), entonces es g( 1 ([x],a) = 2 (g ([x]), a ), lo a [ya] [y]

que se verifica por construccin de los AFMs M1 y M2. Se puede ver que a) g preserva el estado inicial: g ([]) = g ([q1]) = g ([q2]), ya que se ha de verificar g (1 ([q1], ) = 2 (g ([x1], ), [q1] g ([x1])

luego g (q1) = q2 ; g ([]) = q2 b) Igualmente se ve que g preserva los estados de aceptacin.

Bibliografa http://www.dia.fi.upm.es/~jgarcia/it/MaterialDidactico_ficheros/Apuntes/Minimizacion.pdf http://www.dalum.eui.upm.es/apuntes/tecnicas/LPSI/teoria_de_automatas_y_lenguajes_forma les/2022_tema_2.pdf