Antologias Teoria de La Computacion

Teora de la Computacin

INSTITUTO TECNOLOGICO DE DURANGO

DEPARTAMENTO DE SISTEMAS Y COMPUTACION

ANTOLOGIA PARA LA MATERIA DE TEORIA DE LA COMPUTACION (Ingeniera en Sistemas Computacionales)

I.S.C Elda Rivera Saucedo

AGOSTO-DICIEMBRE 2008

_____________________________________________________________________ I.S.C. Elda Rivera Saucedo

1


I introduccin 1.1 Autmatas, computabilidad y complejidad. 1.2 Nociones matemticas. 1.2.1 Conjuntos 1.2.2 Funciones y Relaciones 1.2.3 Cadenas y Lenguajes 1.3 Induccin matemtica. 1.1 Autmatas, computabilidad y complejidad. Un autmata es: Una maquina (mecanismo) de naturaleza formal (solo existe como un mecanismo matemtico) Que acepta una informacin de entrada (input), La procesa (La somete a transformaciones simblicas que pueden adoptar la forma de un calculo o computacin ) y genera un resultado o salida (output) Definir un autmata equivaldra a definir el proceso de transformacin del input en un output, lo que equivale a definir una funcin cuyos argumentos son el input y cuyo valor es el output TIPOS DE AUTOMATAS(1) Hay muchos tipos de autmatas, cada tipo de autmata se asocia a una potencia computacional determinada, es decir a una capacidad dada de resolucin de problemas, de hecho, podemos clasificar los problemas algortmicamente solubles asocindolos al tipo de autmata que resuelve, estos tipos se ordenan en jerarqua de menor a mayor potencial computacional Jerarqua de autmatas: Autmatas finitos (Redes Lgicas) Autmatas intermedios: Autmatas de memoria de pila Autmatas de memoria linealmente limitada Maquinas de Turing TIPOS DE AUTOMATAS (2) Adems, podemos clasificar los autmatas: Por el tipo de proceso que ejecutan Aceptacin o reconocimiento Generacin Por su tipo de causalidad: Determinista _____________________________________________________________________ I.S.C. Elda Rivera Saucedo 2

Teora de la Computacin No Determinista Por el tipo de su almacenamiento de informacin: De tamao fijo De tamao creciente De tamao infinito Por el tipo de la informacin que manejan Discreta Continua

TIPOS DE AUTOMATAS (3) Autmatas aceptadores o reconocedores: Resuelven problemas con respuestas si- no que se modeliza normalmente como la identificacin de dos estados finales uno de aceptacin y otro de rechazo. Autmatas generadores o transductores: Construyen una respuesta especfica (una salida) para el problema planteado Autmatas determinista: La solucin del problema viene unvocamente determinada por las entradas y los estados internos del autmata Autmatas no-deterministas: La respuesta no esta unvocamente determinada

1.1 NOCIONES MATEMTICAS 1.1 CONJUNTOS Un conjunto es una coleccin de objetos llamados elementos del conjunto. Si A es un conjunto y a es un elemento de A utilizaremos la notacin a A (se lee a es un elemento de A). Se usa la notacin b A cuando b no es un elemento de A. Si A contiene exactamente los elementos a1, a2, . . . . ., an, lo indicamos escribiendo A={a1,a2, . . . . ., an}. Un conjunto solo se caracteriza por sus elementos y no por el orden en el cual se listan.


3

Teora de la Computacin Los conjuntos A y B son iguales si contienen los mismos elementos. Por lo tanto si, A={1,2,3} y B={2,1,3} se puede escribir que A=B. Algunas veces es conveniente describir el contenido de un conjunto en trminos de un propiedad que sea caracterstica de todos los elementos del conjunto. Sea P(x) una proposicin sobre x. La notacin {x P(x)}, que se interpreta como el conjunto de todas las x tales que P(x) , denota el conjunto de todos los x para los cuales P(x) es una proposicin verdadera. (Todas las x tienen la propiedad P). Notacin de Conjuntos P = { x | P(x)}. See lee x tal que P(x) es verdadero. A= { x | x es una letra del alfabeto}. A= { a, b, c, d, e, . . . . . . . . . z}. Los conjuntos se representan de dos formas: Por extensin A={a, b, c, d, e, f, g, h, i, j, k, l, m, n, , o, p, q, r, s, . . . . . . . . . . . . } Por comprensin A={x | x es una letra del alfabeto} Conjunto Finito A={a, b, c, d, e, f, g, h, i, j, k, l, m, n, , o, p, q, r, s, t, u, w, x, y, z } Conjunto Infinito B={1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, . . . . . . . . . . . . . . . . . . . . }

1.2 OPERACIONES CON CONJUNTOS Las operaciones habituales que se definen sobre los conjuntos son: El conjunto 0 llamado conjunto vaco o nulo, no tiene elementos. El conjunto vaci es un subconjunto de todos los conjuntos.


4

Teora de la Computacin La unin de conjuntos A y B se denota por A B y es un conjunto formado por los elementos que aparecen en A, en B o en ambos. Por lo tanto A B={x A o x B}. x Por ejemplo, si A={1,2,3} y B={a,b}, entonces A B={1,2,3,a,b}. La interseccin de A y B es el conjunto de todos los elementos que aparecen simultneamente en A y tambin en B. Por lo tanto A B={x A y x B}. x Por ejemplo, si A={1,4,5,7} y B={2,4,7,8}, entonces A B={4,7}. El complemento relativo si Ay B son dos conjuntos cualesquiera, el complemento de B con respecto a A es el conjunto: A-B={ x A y x B}. x Por lo tanto, A-B esta compuesto por todos los elementos de A que no estn tambin, en B. Por ejemplo, si A={0,2,4,6,8,10} y B={0,1,2,3,4}, entonces AB=[6.8.10}, mientras que B-A={1,3}. A , el conjunto de potencia de A, es el conjunto formado por todos los 2 subconjuntos de A. A Por ejemplo, si A={a,b,c}. Entonces 2 ={ o, {a}, {b}, {c}, {a,b}, {a,c}, {b,c}, {a,b,c}}. Dados dos conjuntos A y B, su producto cartesiano, AxB, es el conjunto de todos los pares ordenados de los que el primer elemento proviene de A y el segundo de B. As que, AxB={(a,b) aA y bB}. Por ejemplo, si A={1,2,3} y B{5,6} entonces: AxB={(1,5), (2,5), (3,5), (1,6), (2,6), (3,6)}. Si A y B son conjuntos y todos los elementos de A son tambin elementos de B, se escribe A B y se dice que A es un subconjunto de B. Por ejemplo A={1,2,3} y B={0,1,2,3,4,5}, se tiene A B. Por otro lado B no es un subconjunto de A, porque los elementos 0,4 y 5 de B no lo son de A. Ejemplo: C ={Frutas} S = {frutas ctricas} S C =Y x| x S = >X C Se lee: S es un subconjunto de C o S esta incluido en C si para todo x ( =Y x). Tal que x pertenece al subconjunto de S, implica que x pertenece al conjunto C.


5

Teora de la Computacin La inclusin cuando cualquier elemento de A que este en B, o cualquier elemento de B que este en A, o que sean iguales. Por ejemplo si A={2,4,5,7,8} y B={2,4}, entonces B A={2,4}. La cardinalidad de un conjunto es el numero de elementos de ese conjunto. Por ejemplo si A={a,b} entonces | A | = 2. la cardinalidad del conjunto vaci es 0 porque no tiene ningn elemento. Todos los conjuntos aqu tratados se consideran subconjuntos de un conjunto universal U. Los complementos pueden ser formados con respecto a este conjunto universal. Si A es un conjunto, entonces U-A es el conjunto de todos los elementos que no estn en A. Conviene denotar tales complementos mediante A, de forma que U-A=A. Obsrvese que 0=U y U=0. 1.3 ALFABETOS ( ) Un alfabeto es un conjunto no vaci y finito de smbolos. En el caso del alfabeto ingles, la coleccin definida es el conjunto de las letras del alfabeto junto con los smbolos que se usan para construir palabras en ingles (tales como el guin, el apostrofe y otros por el estilo). Cada smbolo de un alfabeto es una cadena sobre dicho alfabeto. La cadena vaca, la cual se denota por el smbolo , es una palabra sobre cualquier alfabeto.

1.4 PROPIEDADES DE LAS CADENAS O STRINGS Una cadena (o palabra) es una secuencia finita de smbolo. Por ejemplo: a, b y c son smbolos y abcd es una cadena. 1.4.1 Cadena Vaca

La cadena vaca, denotada por , es la cadena que consiste en cero smbolos. Por tanto, tiene longitud || = 0. 1.4.2 Longitud

Si w es una cadena sobre cualquier alfabeto, su longitud se denota como | w | . La longitud de w es el nmero de smbolos que tiene la cadena. Por ejemplo: abcd tiene longitud | w | = 4. 1.4.3 Concatenacin 6



La concatenacin de dos cadenas es la cadena que se forma al escribir la primera seguida de la segunda, sin que haya espacio entre ellas. Por ejemplo: si w=banana y z=rama, la concatenacin de w con z es la cadena bananarama. La concatenacin de las cadenas w y z se denota como wz o w.z. La cadena vaca es la identidad para el operador de concatenacin. Es decir, = w ||= z x= para cada cadena x=casa z=vacio w = roja . Xzw = casa roja xw = casaroja

1.4.4

Potenciak

La nocin de potencia de una cadena sobre un alfabeto es dada por la notacin w que denota la concatenacin de k copias de la cadena w.

Por tanto, si W=122 sobre el alfabeto ={1,2}, se tiene: 0 W = 1 W = 122 2 W = 122122 3 W = 122122122 1.4.5 Igualdad de Cadenas Si w y z con cadenas, se dice que w es igual a z, si tienen la misma longitud y los mismos smbolos en la misma posicin. Se denota mediante w = z. 1.4.6 Prefijo Los prefijos de un cadena esta formados por los primeros smbolos de esta. Por ejemplo, la cadena 121 sus prefijos son: , 1, 12, y 121 con lo que toda palabra puede considerarse prefijo de si misma. Un prefijo de una cadena que no sea la misma cadena es u prefijo propio. 1.4.7 Sufijo Los sufijos de una cadena estn formados por los ltimos smbolos de esta. Por ejemplo, la cadena abc sus sufijos son: , c, bc, abc. Un sufijo de una cadena que no sea la misma cadena es un sufijo propio. _____________________________________________________________________ I.S.C. Elda Rivera Saucedo 7

Teora de la Computacin 1.4.8 Subcadena.

Una cadena w es una subcadena o subpalabra de otra cadena z si existen las cadena x e y para las cuales z = xwy. 1.4.9 Transpuestas

La inversa o transpuesta de una cadena w es la imagen refleja de w. Por ejemplo, si w = able entonces su inversa es elba. Para denotar la inversa de w se usa w`.

EJERCICIOS DE CONJUNTOs

A={1,2,3}A B ={1,2,3,4,5,6} A B = {3} B A = {4,5,6} A B = {1,2}

B={4,5,6,3}

A 3 2 = 2 = 8 {0}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3} B 4 2 = 2 = 16 {0}, {4}, {5}, {6}, {3}, {4,5}, {4,6}, {4,3}, {5,6}, {5,3}, {6,3}, {4,5,6}, {4,5,3}, {5,6,3}, {4,6,3}, {4,5,6,3}

Producto Cartesiano _____________________________________________________________________ I.S.C. Elda Rivera Saucedo 8


(1,4), (1,5), (1,6), (1,3), A x B = (2,4), (2,5), (2,6), (2,3), (2,4), (3,5), (3,6), (3,3) (3,4), (3,5), (3,6), (3,3) (4, 1), (4,2), (4,3) B x A= (5,1), (5,2), (5,3) (6,1), (6,2), (6,3) (3,1), (3,2), (3,3) Cardinalidad | A| =3

| B| =4

Ejercicios de Cadena

Z = {8532} Y= {Galeria} W= {Politica}Ejercicio: Potencia C={15} 0 C = 1 C = 15 2

| Z| =4 | Y| =7 | W| =8

V={Hola} 0 V = 1 V = Hola 2 9



C 3 C

= 1515 = 151515

V = HolaHola 3 V = HolaHolaHola

Ejercicio: Prefijos y Sufijos W= 475 Prefijos W=, 4, 47, 475 R=, l, lo, lop, lope, lopez L=, @, @$, @$% Sufijos W= , 5, 75, 475 R= , z, ez, pez, opez, lopez L= , &, $&, @$% Ejercicion: Longitud Z= 8532 =4 Ejercicio: Concatenacin 8532galeria2y galeriapoliticayv 8532politica2w galeria8532yz politicagaleriawy politica8532wz Ejercicio: Transpuesta A= anita B= roma A = atina B = amor y= galeria =7 w =poltica =8 R= Lpez C =@$&


10

Teora de la Computacin * Es el conjunto de todas las palabras que pueden ser construidas con letras o smbolos de + Es el conjunto de todas las palabras No vacas que pueden ser construidas por . Por ejemplo: Decimos que un lenguaje es denotado por * para el alfabeto = {0,1,2}

II Lenguajes Regulares2.1 Expresiones regulares. 2.2 Lenguajes no regulares. 2.3 Autmatas finitos 2.3.1 Autmatas finitos No determinsticos. 2.3.2 Autmatas finitos determnisticos 2.3.2.1 Autmatas finitos no determinsticos con movimiento (afn- ). 2.3.2.2 Conversin de un afn a un afd 2.1 EXPRESIONES REGULARES Definicin: Es un metodo de representacin para cadenas de caracteres validas en un lenguaje. Una expresin regular, a menudo llamada tambin patrn, es una expresin que describe un conjunto de cadenas sin enumerar sus elementos. Por ejemplo, el grupo formado por las cadenas Handel, Hndel y Haendel se describe mediante el patrn "H(a||ae)ndel". La mayora de las formalizaciones proporcionan los siguientes constructores: una expresin regular es una forma de representar a los lenguajes regulares (finitos o infinitos) y se construye utilizando caracteres del alfabeto sobre el cual se define el lenguaje. Especficamente, las expresiones regulares se construyen utilizando los operadores unin concatenacin y clausura de Kleene.

Terminologa. | Alternacin Una barra vertical separa las alternativas. Por ejemplo, "marrn|castao" casa con marrn o castao. Cuantificacin: _____________________________________________________________________ I.S.C. Elda Rivera Saucedo 11

Teora de la Computacin Un cuantificador tras un carcter especifica la frecuencia con la que ste puede ocurrir. Los cuantificadores ms comunes son +, ? y *: + Mas El signo ms indica que el carcter al que sigue debe aparecer al menos una vez. Por ejemplo, "ho+la" describe el conjunto infinito hola, hoola, hooola, hoooola, etctera. ? Interrogacin El signo de interrogacin indica que el carcter al que sigue puede aparecer como mucho una vez. Por ejemplo, "ob?scuro" casa con oscuro y obscuro. * Asterisco El asterisco indica que el carcter al que sigue puede aparecer cero, una, o ms veces. Por ejemplo, "0*42" casa con 42, 042, 0042, 00042, etctera. Agrupacin: ( ) Parntesis () Los parntesis pueden usarse para definir una concatenacin con los dems operadores. Por ejemplo, "(p|m)adre" es lo mismo que "padre| madre", y "(des)?amor" casa con amor y con desamor. [ ] Corchetes Los corchetes se utilizan como opcion Por ejemplo: a[b]c, que forma las cadenas abc o ac. Los constructores pueden combinarse libremente dentro de la misma expresin, por lo que "H(ae?|)ndel" equivale a "H(a|ae|)ndel". La sintaxis precisa de las expresiones regulares cambia segn las herramientas y aplicaciones consideradas, y se describe con ms detalle a continuacin. Su utilidad ms obvia es la de describir un conjunto de cadenas, lo que resulta de utilidad en editores de texto y aplicaciones para buscar y manipular textos. Muchos lenguajes de programacin admiten el uso de expresiones regulares con este fin. Por ejemplo, Perl tiene un potente motor de expresiones regulares directamente incluido en su sintaxis. Las herramientas proporcionadas por las distribuciones de Unix (incluyendo el editor sed y el filtro grep) fueron las primeras en popularizar el concepto de expresin regular.

Caractersticas de las expresiones regulares. 1.- Proporciona una notacin clara y concisa para componentes lxicos. 2.- Puede construir automticamente analizadores lxicos eficientes a partir de expresiones regulares.


12

Teora de la Computacin 3.- tiles para representar las estructuras de las construcciones o componentes lxicos de los identificadores, constantes y las palabras reservadas. Ejemplos de autmatas con sus expresiones regulares: La siguiente Expresin regular forma enteros, reales y reales con notacin cientfica. d+[. d+[ E(+ | -) dd] ] la d representa digito. Algunas cadenas formadas por la expresin son: 33 , 234.34 , 34.34E+02. El siguiente autmata representa la expresin regular anterior

d q0 d b100

d

q1

.

q20

d b

q3

E

q4

+, -

q5

d

q6

d b

q7

200

300

100 200 300

Entero Real Real con Notacin Cientfica


13

Teora de la Computacin El lenguaje del siguiente autmata, esta formado por cualquier cadena de 1s, incluyendo . 1 q0

La expresin regular del autmata es: 1*

El lenguaje del siguiente autmata esta formado por todas las cadenas de as de longitud par, incluyendo . a q0 a La expresin regular del autmata es: (aa)* El lenguaje del siguiente autmata esta formado por cadenas de cero ms as seguidas de cero ms bs. a b q0 q1 b q1

La expresin regular del autmata es: a*b*.


14


bq1

aq0

a a b bq2

La expresin regular del autmata es (a(a|b)+ | b+[ a(b+ | a(a|b)+)]) Existen muchas equivalencias con respecto a expresiones regulares basadas en las correspondientes igualdades de lenguajes. Por ejemplo: 1. a[ b]+ = a(b)* 2. x ( y+| z+) = ( x y+ | x z+) 3. (r*)* = r* 2.2LENGUAJES NO REGULARES Lenguaje regular Un lenguaje regular es un tipo de lenguaje formal que satisface las siguientes propiedades: Puede ser reconocido por: un autmata finito determinista un autmata finito no determinista 15


Teora de la Computacin un autmata finito alterno una mquina de Turing de solo lectura

Es generado por: una gramtica regular una gramtica de prefijos

Es descrito por: una expresin regular

Lenguajes regulares sobre un alfabeto Un lenguaje recursivo sobre un alfabeto dado se define recursivamente como: El lenguaje vaco es un lenguaje regular El lenguaje cadena vaca {} es un lenguaje regular Para todo smbolo a {a} es un lenguaje regular

Si A y B son lenguajes regulares entonces A B (unin), AB (concatenacin) y A* (clausura o estrella de Kleene) son lenguajes regulares Si A es un lenguaje regular entonces (A) es el mismo lenguaje regular No existen ms lenguajes regulares sobre Todo lenguaje formal finito constituye un lenguaje regular. Otros ejemplos tpicos son todas las cadenas sobre el alfabeto {a, b} que contienen un nmero par de aes o el lenguaje que consiste en varias aes seguidas de varias bes. Si un lenguaje no es regular requiere una mquina con al menos una complejidad de (log log n) (donde n es el tamao de la entrada). En la prctica la mayora de los problemas no regulares son resueltos con una complejidad logartmica. Un lenguaje formal infinito puede ser regular o no regular. El lenguaje L = {an, n > 0} es regular porque puede ser representado, por ejemplo, mediante la expresin regular a+. El lenguaje L= {an bn, n > 0} es un lenguaje no regular dado que no es reconocido por ninguna de las formas de representacin anteriormente enumeradas. _____________________________________________________________________ I.S.C. Elda Rivera Saucedo 16


Propiedades de cierre Los lenguajes regulares son cerrados con las siguientes operaciones, de modo que si L y P son lenguajes regulares los siguientes lenguajes tambin sern regulares: El complemento de L La clausura o estrella de Kleene L* de L El homomorfismo (L) de L La concatenacin L'P de L y P La unin L P de L y P La interseccin L P de L y P La diferencia L \ P de L y P El reverso LR de L

Decidir cundo un lenguaje es regular Para situar los lenguajes regulares en la jerarqua de Chomsky hay que notar que todo lenguaje regular es tambin un lenguaje independiente de contexto, aunque la afirmacin contraria no es cierta, por ejemplo: el lenguaje que contiene el mismo nmero de aes y de bes es independiente de contexto pero no regular. Para probar que un lenguaje de este tipo no es regular se usa el teorema de Myhill-Nerode, o el lema de bombeo por ejemplo. Hay dos aproximaciones puramente algebraicas para definir lenguajes regulares. Si es un alfabeto finito y * es un monoide libre consistente en todas las cadenas sobre , f: * M es un monoide simtrico donde M es un monoide finito y S es un subconjunto de M entonces el conjunto f-1(S) es regular. Todo lenguaje regular se presenta de esta manera. Si L es un subconjunto de *, se define la relacin equivalente ~ en * de la siguiente manera: u ~ v significa uw L si y solo si vw L para todo w *


17

Teora de la Computacin El lenguaje L es regular si y solo si el nmero de clases de equivalencia de ~ es finito; si este es el caso, este nmero es igual al nmero de estados del autmata determinista mnimo que reconocer L. Lenguajes finitos Un subconjunto especial de los lenguajes regulares es el de los lenguajes finitos, aquellos que solo contienen un nmero finito de palabras. Estos son lenguajes obviamente regulares y uno podra crear expresiones regulares que seran la unin de todas las palabras del lenguaje que definiran dicho lenguaje.

2.3 Autmatas finitosEl termino maquina evoca algo hecho en metal, usualmente ruidoso y grasoso, que ejecuta tareas repetitivas que requieren de mucha fuerza o velocidad o precisin. Ejemplos de estas mquinas son las embotelladoras automticas de refrescos. Su diseo requiere de conocimientos en mecnica, resistencia de materiales, y hasta dinmica de fluidos. Al disear tal mquina, el plano en que se le dibuja hace abstraccin de algunos detalles presentes en la mquina real, tales como el color con que se pinta, o las imperfecciones en la soldadura. El plano de diseo mecnico de una mquina es una abstraccin de sta, que es til para representar su forma fsica. Sin embargo, hay otro enfoque con que se puede modelar la mquina embotelladora: cmo funciona, en el sentido de saber qu secuencia de operaciones ejecuta. As, la parte que introduce el liquido pasa por un ciclo repetitivo en que primero introduce un tubo en la botella, luego descarga el lquido, y finalmente sale el tubo para permitir la colocacin de la cpsula (corcholata). El orden en que se efecta este ciclo es crucial, pues si se descarga el lquido antes de haber introducido el tubo en la botella, el resultado no ser satisfactorio. El modelado de una mquina en lo relacionado con secuencias o ciclos de acciones se aproxima mas al enfoque que adoptaremos en este tema. Las mquinas que estudiaremos son abstracciones matemticas que capturan solamente el aspecto referente a las secuencias de eventos que ocurren, sin tomar en cuenta ni la forma de la mquina ni sus dimensiones, ni tampoco si efecta movimientos rectos o curvos, etc. En esta parte estudiaremos las mquinas abstractas mas simples, los autmatas finitos, las cuales estn en relacin con los lenguajes regulares, como veremos a continuacin.

Descripcin informal del Funcionamiento de los autmatas finitosSe le llama autmata finito, por que nos lleva a un termino o a un fin y nos sirve para representar un flujo de informacin o un estimulo, para formar cadenas pertenecientes a un lenguaje. Un lenguaje es el conjunto de cadenas aceptadas por un autmata. Sin embargo un Lenguaje no esta asociado a un nico _____________________________________________________________________ I.S.C. Elda Rivera Saucedo 18

Teora de la Computacin autmata. Es mas , a un mismo lenguaje le podemos asociar siempre muchos autmatas que reconocen las cadenas en el.

Flujo de informacin q0 Estado inicial o Estimulo q1 Estado final

Nota: Los estados representados por dos crculos indican estados de aceptacin

El funcionamiento de los autmatas finitos consiste en ir pasando de un estado a otro, a medida que va recibiendo los caracteres de la palabra de entrada. Este proceso puede ser seguido fcilmente en los diagramas de estados. Simplemente hay que pasar de estado a estado siguiendo las flechas de las transiciones, para cada carcter de la palabra de entrada, empezando por el estado inicial. Por ejemplo, supngase que tenemos el autmata de la figura A la palabra de entrada bb. El autmata inicia su operacin en el estado q0 que es el estado inicia y al recibir la primera b pasa al estado q2, pues en el diagrama hay una flecha de q0 a q2 con la letra b. Luego, al recibir la segunda b de la palabra de entrada, pasara del estado q2 a el mismo, pues en la figura se puede ver una flecha que de q2 regresa al mismo estado, con la letra b. Podemos visualizar el camino recorrido en el diagrama de estados como una trayectoria recorrida de estado en estado. Por ejemplo, para el autmata finito de la figura A la trayectoria seguida para la palabra ab consiste en la secuencia de estados: q0, q1, q1. Los estados son el nico medio de que disponen los AF (Autmatas Finitos) para recordar los eventos que ocurren (por ejemplo, qu caracteres se han ledo hasta el momento); esto quiere decir que son maquinas de memoria limitada. En ltima instancia, las computadoras digitales son mquinas de memoria limitada, aunque la cantidad de estados posibles de su memoria podra ser enorme.


19


bq1

aq0

a a b bq2

Fig. A Notacin Grafica Definicin: Un Automata es: Una maquina (mecanismo) de naturaleza formal (solo existe como un mecanismo matemtico ) Que acepta una informacin de entrada (input), La procesa (La somete a transformaciones simblicas que pueden adoptar la forma de un calculo o computacin ) y genera un resultado o salida (output) Definir un autmata equivaldra a definir el proceso de transformacin del input en un output, lo que equivale a definir una funcin cuyos argumentos son el input y cuyo valor es el output. Definicin: Un autmata finito es un modelo matemtico formado por un quntuplo (Q, , , q0, F) donde: Q es un conjunto finito de estados. un alfabeto de entrada finito. q0 elemento de Q , el estado inicial. F Q el conjunto de estados finales o de aceptacin. es la funcin : Q x Q que determina el nico estado siguiente para el par (q1, ) correspondiente al estado actual q1 y la entrada .


20


2.3.1 AUTMATAS FINITOS DETERMINSTICOS (AFD).1. 2. 3. 4. 5. Un autmata finito determinstico es un quintuplo (Q, , , q0, F) donde: Q es un conjunto finito de estados. un alfabeto de entrada finito. q0 elemento de Q , el estado inicial. F Q el conjunto de estados finales o de aceptacin. es la funcin : Q x Q que determina el nico estado siguiente para el par (q1, ) correspondiente al estado actual q1 y la entrada . Generalmente el trmino autmata finito determinstico se abrevia como DFA de sus siglas en ingls Deterministic Finite Automaton. Usaremos M = (Q, , q0, F, ) para indicar el conjunto de estados, el alfabeto, el estado inicial, el conjunto de estados finales y la funcin asociadas con la M (maquina o autmata ) del AFD. Se puede construir un diagrama para que ayude a determinar los distintos miembros o cadenas del lenguaje. Tal diagrama tiene la forma de un grafo dirigido con informacin aadida, y se llama diagrama de transicin. Los nodos del grafo corresponden a los estados del AFD y se usan para sealar, en ese momento, hasta qu lugar se analiz la cadena. Por lo general q 0 es el estado inicial, marcando con una flecha (), el comienzo del autmata; algunos estados estn designados como final o aceptacin indicados por un doble crculo. Los smbolos del alfabeto son las etiquetas de los arcos del grafo. Si cuando ha sido tratada la cadena en su totalidad se termina en un estado de aceptacin entonces la cadena es aceptada por el lenguaje. Si M es un AFD, entonces el lenguaje aceptado por M es L(M)={w * es aceptada por M}. Por tanto, L(M) w es el conjunto de cadenas que hacen que M pase de su estado inicial a un estado de aceptacin. _____________________________________________________________________ I.S.C. Elda Rivera Saucedo 21 Las caractersticas de los autmatas finitos determinsticos son: Un conjunto finito de estados y un conjunto de transiciones de estado a estado, que se dan sobre smbolos de entrada tomados de un alfabeto . Para cada smbolo de entrada existe exactamente una transicin a partir de cada estado (posiblemente de regreso al mismo estado). Un estado, por lo general denotado como q0 es el estado inicial, en el que el autmata comienza. Algunos estados (tal vez ninguno) estn designados como final o de aceptacin.

Teora de la Computacin Un AFD es un caso especial de un autmata finito no deterministico (AFND) en el cual: 1.- Ningn estado tiene una transicin vaci 2.- Para cada estado q y cada smbolo de entrada a, hay a lo sumo una arista etiquetada con a que sale del estado q Un AFD tiene una transicin desde cada estado con cualquier entrada. Si se esta usando una tabla de transiciones para representar la funcin de transicin de un AFD entonces cada entrada en la tabla de transiciones es un solo estado . Como consecuencia es muy fcil determinar si un autmata finito determinista acepta o no una cadena de entrada puesto que hay un camino desde el estado de inicio con esa cadena . Ejemplo 1: El lenguaje que acepta el AFD esta formado por todas las cadenas sobre el alfabeto = {a, b}, siempre y cuando terminen con a. Q = {q0, q1}, = {a, b}, q0 = q0 , F = {q1} y se define mediante la tabla de la figura 1.1 ( Tabla de transiciones o Matriz de Transicin ). Matriz de Transicin o Tabla de Transiciones : Es una matriz bidimensional (Q \ )= en donde del lado de las columnas esta el alfabeto de entrada y los reglones representan los estados del autmata Nos sirve para representar las transiciones en el autmata. q0 q1Q3

a q1 q1

b q0 q0

Figura 1.1. Diagrama de Transicin (Autmata). b a a

q0

q1 b


22


Ejemplo 2 : El lenguaje que acepta el AFD esta formado por todas las cadenas sobre el alfabeto = {a, b}. En donde: Q = {q0, q1, q2}, = {a, b}, q0 = q0 , F = {q1, q2} y se define mediante la tabla de la figura 2.1 ( Tabla de transiciones o Matriz de Transicin ) o bien para una cadena en especifico como seria la cadena abb = para la cadena abb q0,a = { q1 } q1,b = { q1} q1,b = { q1} cadena aceptada, ya que el estado 1 es de aceptacin . bq1

aq0

a a b bq2

q0 q1 q2

A q1 q1 q0 Figura. 2

B q2 q1 q2


23


Ejemplo 3: El AFD M = {Q, , q0, F, } acepta el lenguaje L(M) = {w {a, b}* que no contiene tres bs consecutivas} y esta representada por: Q={q0, q1, q2, q3} ={a, b} q0=q0 F={q0, q1, q2} y dada por la tabla de la figura 3.1. q0 q1 q2 q3Q3

a q0 q0 q0 q3

b q1 q2 q3 q3

Figura 3.1. El diagrama de transicin correspondiente se muestra en la figura 3.2. a b q0 a q1 b q2 b q3 a, b

a Figura 3.2


24


Ejemplo 4 : El lenguaje que acepta el AFD esta formado por todos los nmeros tales como enteros, reales, y reales con notacin cientfica sobre alfabeto = {d(representa un digito), . , E, +,- }. En donde se utiliza el blanco como delimitador entre un numero y otro al momento de analizar En donde: Q = {q0, q1, q2, q3, q4, q5, q6, q7 } = {d, . , E, +,- } q0= q0 F = {200,300,400} se define mediante la tabla de la figura 4.1

d q0 d b100

d

q1

.

q20

d b

q3

E

q4

+, -

q5

d

q6

d b

q7

200

300

100 200 300

Entero ( ejem. 31416 ) Real (ejem. 3.14 ) Real con Notacin Cientfica (ejem. 3.1416E-03)

b : es un Delimitador (blanco) el cual nos indica hasta donde analizar la cadena. Ejemplo: Cuando escribimos una carta, para separar entre una palabra y otra , utilizamos el espacio en blanco, igual en nuestro lenguaje podemos separar entre una cadena de caracteres y otra por medio de un blanco para as especificar hasta donde se analizaran nuestras cadenas, igual podra ser una tabulador o un enter, etc. en el diseo de nuestro lenguaje nosotros especificamos cual ser nuestro delimitador


25


Nota: 3.14 es una cadena de caracteres la cual forma un Entero

Definicin : Token: A una secuencia de caracteres que tiene un significado colectivo se le conoce con el nombre de Token. Es el resultado final de analizar una cadena de caracteres dentro de un lenguaje a la cual se le asigna un nombre. Es el resultado generado por el Analizador Lxico para un determinado lenguaje el cual definir cuando se ha llegado a un estado de terminacin valido o incorrecto. Definicin: Analizador Lxico Llamado tambin anlisis lineal, es el proceso de exploracin en el cual la cadena de caracteres que constituye el programa fuente se lee de izquierda a derecha y se agrupa en componentes lxicos .

Q\ 0

d 1

. error

E error

+ error

Error

blanco error 26


Teora de la Computacin 1 2 3 4 5 6 7 1 3 3 error 6 7 error 2 error error error error error error error error 4 error error error error error error error 5 error error error Error Error error 5 error error error 100 error 200 error error error 300

Nota: Los estados 100,200,300 son los estados de Aceptacin

Figura 4.1

2.3.2 AUTMATAS FINITOS NO DETERMINISTICOS (AFN) Definicin: Un AFN se puede representar diagramticamente mediante un grafo de transiciones en el que los nodos son los estados y las aristas etiquetadas representan la funcin de transicin. Este grafo se parece a un diagrama de transiciones que para el mismo carcter puede etiquetar 2 o mas transiciones fuera de un estado y las aristas pueden etiquetarse con el smbolo especial vaci ( o ) y con smbolos de entrada. Definicin: Un autmata finito no determinstico es un quintuplo ( Q, , q0, , F) en donde Q, , q0 y F (estados, entradas, estado inicial y estados finales) poseen el mismo significado que para un AFD, pero en este caso es una transformacin de Q x a 2Q. (Recurdese que 2Q es el conjunto de potencias de Q, el conjunto de todos los subconjuntos de Q). Obsrvese que puesto que es una relacin para todo par (q, ) compuesto por el estado actual y el smbolo de la entrada, (q, ), es una coleccin de cero o ms estados [es decir, (q, )Q]. Esto indica que, para todo estado q1 se pueden tener cero o ms alternativas a elegir como estado siguiente, todas para el mismo smbolo de entrada. _____________________________________________________________________ I.S.C. Elda Rivera Saucedo 27

Teora de la Computacin Generalmente el trmino autmata finito no determinstico se abrevia como NFA de sus siglas en ingls Nondeterministic Finite Automaton. Si M es un NFA, definiremos el lenguaje aceptado por M por medio de L(M)={w es una w cadena aceptada por M} donde una cadena w es aceptada por M, si M pasa de su estado inicial a su estado de aceptacin o final al recorrer la cadena w (w es consumida en su totalidad). Observe ahora el diagrama de transicin de la figura 5.1 a q0 a b q3 b Figura 5.1 El AFN descrito anteriormente acepta el lenguaje formado por cualquier nmero (incluyendo el cero) de as, concatenadas a una b una a concatenada a cualquier numero (incluyendo el cero) de bs . Se representa de la siguiente forma: Q={q0, q1, q2, q3, q4} F={q2, q3, q4} q0=q0 ={a, b} Y dada por la tabla de la figura 5.2. q4 a b q2

q1

Estados q0 q1 q2 q3 q4Q3

a {q1, q4} {q1} error error error

b {q3} {q2} error error { q4} 28


Teora de la Computacin Figura 5.2. Obsrvese que en el contenido de las celdas de la tabla de transicin de la figura 5.2. son conjuntos. El hecho de que existan celdas con error, indica que no existe ninguna transicin desde el estado actual mediante la entrada correspondiente. Que para un par (estado actual, entrada) exista ms de un posible estado siguiente indica que se puede elegir entre las distintas posibilidades. En el modelo no existe nada que determine la eleccin. Por esta razn, se dice que el comportamiento del autmata es no determinista. Para analizar la cadena abba las transiciones serian las siguientes (q0,a )= { q1, q4} ( Elegimos una de las 2, en este caso sera q1) (q1,b )= { q2 } (q2,b )= { error} Obsrvese que no llegamos a un estado de aceptacin eligiendo por el camino de q1 en donde se nos da la opcin de elegir cualquiera de los 2 estados { q1, q4} Ahora bien debemos elegir el otro estado para verificar si por este otro camino dicha cadena seria valida o no . Analizando..... (q0,a )= { q1, q4} ( Elegimos una de las 2, en este caso ahora tomaremos el estado q4) (q4,b )= { q4 } (q4,b )= { q4 } (q4,a )= { error} Por este camino tampoco se llega a un estado de aceptacin por lo que se concluye que la cadena abba no es valida para este lenguaje Aqu es donde notamos como un AFN nos da la opcion de 2 caminos a elegir por lo que se necesita hacer el seguimiento por los 2 caminos para determinar si es o no valida la cadena , ya que puede darse el caso que por un camino no sea valida y por otro si , por esta razon se dice que es un AF no determinista , ya que no nos determina el camino a seguir como lo hace un AFD, este nos da un solo camino desde el estado de inicio al final para una cadena , es decir nos determina el camino a seguir.

Ejemplo 6: Consideremos el AFN M={ Q, , q0, F, } que acepta el lenguaje formado por cadenas que tienen cero o ms ocurrencias de ab aba y esta dado por: _____________________________________________________________________ I.S.C. Elda Rivera Saucedo 29

Teora de la Computacin Q={q0, q1, q2} ={a, b} q0=q0 F={q0} Y dada por la tabla de la figura 6.1. Este NFA tiene el correspondiente diagrama de transicin que se muestra en la figura 6.2.

Estados q0 q1 q2Q3

a {q1} error {q0}

b error {q0, q2} error

Figura 6.1.

a b q0 q1

a

q2

b

Figura 6.2. Ejemplo 7: Consideremos el AFN M = { Q, , q0, F, } que acepta el lenguaje formado por cadenas que tienen cero o ms ocurrencias de a b y estas tienen la terminacin abb dado por el siguiente diagrama de transiciones a q0 a q1 b q2 b q3 30

_____________________________________________________________________ I.S.C. Elda Rivera Saucedo b


En donde: Q = { 0,1,2,3 } q0 = {0} F = {3} = {a ,b} = para la cadena abb q0,a = {0,1 }, q1,b = {2}, q2,b = {3}

cadena aceptada en el estado 3

2.3.2.1 AUTMATAS FINITOS NO DETERMINSTICOS CON MOVIMIENTO (AFN- ). Un autmata finito no determinstico con movimiento (entrada vaca) es como el quintuplo ( Q, , , q0, F) con todos sus componentes igual que a un AFN, con excepcin de , la funcin de transicin, que ahora transforma Q x ( {}) a 2Q; para incluir transiciones de un estado a otro que no dependan de ninguna entrada. Se puede aadir una columna en la tabla de para colocar los pares de la forma (qi, ). Cuando hay -transiciones en un AFN es conveniente suponer que cada estado tiene una -transicin que cicla en ese estado. El siguiente diagrama de transicin representa un AFN- que acepta el lenguaje L(M) = { w {a, b} que contiene solo una o mas as consecutivas o una o mas bs consecutivas } a 0 3 b 4 1 a 2 b

En donde: Q = { 0,1,2,3,4 } q0 = {0} F = {2,4} = {a ,b, } = para la cadena bb : (q0, )={1,3}, (q3,b) ={4}, (q4,b) = {4} cadena aceptada en el estado 4 Observe el ejemplo del diagrama de transicin de la figura 7.1, que acepta el lenguaje consistente en cualquier nmero (incluyendo el cero) de 0s seguidos _____________________________________________________________________ I.S.C. Elda Rivera Saucedo 31

Teora de la Computacin por cualquier nmero de 1s seguido, a su vez, por cualquier nmero de 2s y cuya tabla de transicin es mostrada por la figura 7.2. 0 q0 1 q1 2 q2

Figura 7.1

Q \ q0 q1 q2Q3

0 {q0} error error

1 error {q1} error

2 error error {q2}

{q1} {q2} error

Figura 7.2 Ejemplo 8: El siguiente diagrama de transicin acepta el lenguaje formado por cadenas que tienen cero o ms ocurrencias de ab aba.

a q0 q1

a,

q2

b

El AFN- anterior tendra la siguiente tabla de transicin Q \ q0 q1Q3

a {q1} error

b error {q2}

error error 32

{q0} q2 {q0} error _____________________________________________________________________ I.S.C. Elda Rivera Saucedo


TEOREMAS Teorema1.- Cualquier conjunto aceptado por un AFN- ser aceptado por un AFD a AFN- 0 3 b 4 1 a 2 b 0 b 2 a 1 b a

AFD

Teorema 2.-Cualquier conjunto aceptado por un AFN ser aceptado por un AFD a 0 a 1 0 a 1 a

AFN

AFD

Teorema 3.- Sea M = ( Q, , q0, , F) a un AFN. Entonces existe un AFD M = ( Q, , q0, , F) que es equivalente a M. Teorema 4.- Si L es aceptado por un AFN con transiciones vaco(), entonces L es aceptado por un AFN sin transiciones vaco(). AUTMATA FINITO DETERMINISTICO (AFD)


33

Teora de la Computacin Ventajas: Es muy fcil determinar si un AFD acepta o no una cadena de entrada puesto que hay un solo camino desde el estado de inicio etiquetado con esa cadena Desventaja: Por lo general es mas difcil el diseo de un AFD que el de una AFN AUTMATA FINITO NO DETERMINISTICO (AFN) Ventajas: La tabla de transiciones proporciona rpido acceso a las transiciones de un determinado estado en un carcter dado. Desventajas: Puede ocupar gran cantidad de estados cuando el alfabeto de entrada es grande y la mayora de las transiciones son hacia el conjunto vaci. 2.3.2.2CONVERSION DE UN AFN A UN AFD Se dice que dos autmatas son equivalentes si aceptan el mismo lenguaje. Un AFD puede ser fcilmente un AFN, con solo agregar transiciones vaci () que no alteren a este o bien 2 transiciones a estados diferentes, igual sin alterar el lenguaje aceptado por dicho AFD , pero no viceversa. Sin embargo, existe un procedimiento para convertir un AFN a un AFD. Un AFD es un AFN debido a que cumple las caractersticas de sus parmetros, sin embargo cuando queremos transformar un AFN en un AFD, debemos cuidar las transiciones. Es vlida la transformacin y siempre es posible realizarla. Los AFD son los mas sencillos de construir, por lo tanto, puede ser til disear un autmata complejo como un AFN con o sin transiciones para luego transformarlo a un AFD para su implementacin. En la conversin de un AFN a un AFD el AFD esta formado por estados que son un conjunto de estados del AFN Ejemplo: Convertir el siguiente AFN en un AFD


34


b 0 b 1 a 2AFN

aEl primer paso es determinar el estado de inicio del nuevo autmata, por lo que vamos a dar el nombre de los nuevos estados, con las letras del alfabeto para no confundirlos con los estados del AFN , as que para el estado de inicio ser la letra A y as sucesivamente como se vayan generando los nuevos estados. Entonces el estado A estar formado por el estado de inicio del AFN mas todos los estados que me lleven con una transicin desde el estado de inicio a otros estado nicamente con el vaci si es que hubiera alguna transicin. Para este autmata no es el caso entonces nuestro estado de inicio quedara de la siguiente forma: A = {0} Siguiente paso, hacer el anlisis de transiciones en el AFN con cada una de las entradas del alfabeto partiendo del estado A, que en este caso es el estado 0 del AFN ; entonces del estado 0 con una a no existe transicin y del estado 0 con una b existe una transicin al estado 1 y al estado 2 por lo que quedara de la siguiente forma : A, a = { } A, b = { 1,2} = B El conjunto formado por el estado 1 y 2, ser un nuevo estado al cual le daremos el nombre de B, para llevar una secuencia de las letras del alfabeto, ste ser analizado de la misma forma que el estado A, y as sucesivamente con cada estado nuevo que se genere, hasta no tener nuevos estados que analizar, recordando que se analiza con cada entrada del alfabeto del AFN aun y cuando no hay transicin, es conveniente hacer el anlisis para evitar que se nos pase alguna transicin. Ahora analicemos B; que son los estados 1 y 2 , del estado 1 hay una transicin con a al estado {0,2 y del estado 2 no hay transicin con a entonces solo estar formado por {0,2}, que es un nuevo conjunto de estados al cual le daremos el nombre de C, Ahora analicemos B(Estados 1,2) con b, de los estados 1 y 2 no existe ninguna transicin con el smbolo b, entonce el estado B quedaria de la siguiente forma: _____________________________________________________________________ I.S.C. Elda Rivera Saucedo 35

Teora de la Computacin B,a = {0,2} = C B,b = { } As se analizara cada uno de los nuevos estados que resulte y se tiene: A, a = { } A, b = { 1,2} = B B, a = {0,2} = C B, b = { } C, a = { } C, b = {1,2 }=BNota: decamos que los nuevos estados del autmata sern un conjunto de estados del AFN por tal motivo los representamos entre llaves, que indican conjunto.

Con los nuevos estados resultantes se disea el autmata nuevo que deber ser un AFD y este deber analizar todas y cada una de las cadenas que analiza el el anterior autmata el AFN y de igual forma las cadenas que este no acepte el nuevo autmata tampoco las deber aceptar. Los estados de aceptacin para el nuevo autmata sern todos aquellos estados que contengan el estado de aceptacin del autmata original, es decir los que contengan el estado 2 que para este caso lo contienen el B y el C El autmata resultante es: b a b representado en conjunto de estados es: b a b Conversin de un AFN- a un AFD Se siguen los mismos pasos que para la conversin anterior , en este autmata si utilizaremos las transiciones vaci ( o ), para pasar de un estado a otro sin cargar ningn carcter, y solo tomar el que necesitemos analizar. Ejemplo: _____________________________________________________________________ I.S.C. Elda Rivera Saucedo 36 AFD Dddd dD

A

B

C

0

1,2

0,2

Teora de la Computacin Convertir el siguiente AFN- a un AFD a AFN- 0 3 b 4 1 a 2 b

A = {0, mas todos los estados a los que se puede llegar con el smbolo } Entonces: A = {0,1,3} Analizando...... A, a = {2} = B A, b = {4} = C B, a = {2} = B B, b = { } C, a = { } C, b = {4} = C Nota: No se hace el anlisis con el solo se utiliza para pasar de un estado a otro.

a a A b C b B AFD


37


Actividades a realizar por el alumno: Buscar y analizar acerca de lo que es un autmata y cuales son los diferentes tipos que hay analizar y desarrollar ejercicios de Autmatas a partir de expresiones regulares dadas y anlisis de los mismos. Realiza ejercicios para la representacin de lenguajes por medio de AFN, AFN- , AFD y expresiones regulares .

EJERCICIOS. * Ejercicio resuelto para su anlisis. b *2.1. Describa el lenguaje aceptado por el DFA representado por el diagrama de transicin de la figura 2.19 a q0 q1 b a q2 _____________________________________________________________________ I.S.C. Elda Rivera Saucedo a, b

38


Figura 2.19. El lenguaje esta formado por cadenas que tienen cero o ms ocurrencias de ab y su expresin regular es (ab)*. 2.2. Construya el diagrama de transicin y describa el lenguaje que acepta el siguiente autmata finito determinstico: Sea M={Q, , q0, F, } dado por: Q = {q0,q1,q2,q3} = {0,1} F = {q0} q0 = q0 y dada por la tabla de la figura 2.20. q0 q1 q2 q3 0 q2 q3 q0 q1 1 q1 q0 q3 q2

Figura 2.20. 2.3. Proporcione los DFAS que acepten los siguientes lenguajes sobre el alfabeto {0,1}: a) El conjunto de todas las cadenas que terminen en 00 0, 1 0, 1 b) El conjunto de todas las cadena que posean tres 0s consecutivos. 0 0 q4 q0 q3 *2.4. Dado ={0, 1} construya el diagrama (ver figura 2.21.) y tabla de transicin (ver figura 2.22) para el AFN que acepte el lenguaje formado por todas las cadenas que contengan dos ceros dos unos consecutivos. 1 q1 1 a 39

_____________________________________________________________________ q2 I.S.C. Elda Rivera Saucedo 0, 1


Figura 2.21. Figura 2.22. Estados/ Alfabeto q0 q1 q2 q3 q4 0 { q0, q3} error {q2} {q4} {q4} 1 { q0, q1} {q2} {q2} error {q4}

2.5. Sea M el AFN dado por Q = {q 0, q1}, ={a,b}, q0= q0, F={q1} y dada en la figura 2.23. Determinar si la cadena ba estan en L(M). Dibujar el diagrama de transicin para M. Estados q0 q1 a {q0, q1} Figura 2.23. b {q1} {q0, q1}


40

Teora de la Computacin *2.6. Construya los diagramas de transicin para los AFN con movimiento y describa su lenguaje. 1 q3

q0

q1

q2

1* L={Cualquier cadena de 1s incluyendo } a q0 b q1

Figura 2.24. a*b* L={Cadenas de cero o ms as concatenadas a cadenas de cero o ms bs}

2.7. Construya la tabla de transicin y describa el lenguaje que acepta el AFN con movimiento , dado el diagrama de transicin de la figura 2.24. q0 a b q1 b a q2 a q3

b

b q5 q4 _____________________________________________________________________ I.S.C. Elda Rivera Saucedo

41


*2.8. Encontrar las expresiones regulares correspondientes a las figuras 2.25, 2.26, 2.27 y 2.28 a,b q0

Figura 2.25.

(a | b)*

L={Cadenas sobre ={a, b}, que tienen cero () ms ocurrencias de as bs}

a,b q0 a q1

b Figura 2.26. b*a(a|b)* L={Cadenas sobre ={a,b}, que contienen al menos una a} a q0 a _____________________________________________________________________ I.S.C. Elda Rivera Saucedo 42 q1


Figura 2.27. (aa)* L={Cadenas de as de longitud par, incluyendo }

a b q0

b a q1

a, b q2

Figura 2.28. A*b* L={Cadenas de cero o ms as concatenadas a acero o ms bs}

Criterios de Acreditacin: Anlisis de los temas.............................................................................. .......10% Tareas (Ejercicios Resueltos)........................................................................ 30%. Herramienta generadora de cdigo libre de errores a partir de autmatas.....30% Examen escrito...............................................................................................30%


43


III Lenguajes Libres De Contexto 3.1 Gramticas libres de contexto. 3.2 rboles de derivacin. 3.3 Formas normales de Chomsky. 3.4 Formas normales de Greibach. 3.5 Eliminacin de Factores Comunes izquierdos. 3.6 Eliminacin de recursividad izquierda. 3.7 Eliminacin de la ambigedad. 3.8 Autmatas Push-Down. 3.9 Lenguajes no regulares. 3.1 Gramticas Libres de Contexto Que es una Gramtica.? _____________________________________________________________________ I.S.C. Elda Rivera Saucedo 44

Teora de la Computacin Una gramtica es un conjunto finito de reglas que determinan un lenguaje. El lenguaje determinado por una gramtica G se denotara por L(G) si L(G1)=L(G2) entonces G1=G2 son equivalentes Una gramtica es un cudruplo G = {VT ,VN , S ,P} En donde: VT = Conjunto finito de smbolos o elementos terminales VN = Conjunto finito de smbolos o elementos no terminales S = Produccin inicial que pertenece a VN P = Conjunto de producciones o de reglas de derivacin . Todos las cadenas del lenguaje definido por una gramtica estn formadas con smbolos terminales (VT) El conjunto de smbolos no terminales (VN ) son smbolos introducidos como elementos auxiliares para la definicin de la gramtica dentro de los cuales se encuentra S que es el smbolo inicial a partir del cual se aplican las reglas de la gramtica para obtener las distintas cadenas del lenguaje . Las producciones son las reglas que se aplican para obtener las cadenas del lenguaje. El conjunto de producciones P se define por medio de la enumeracin de las distintas producciones, en forma de reglas o por medio de un metalenguaje por ejemplo BFN (Backus Naur Form ) Ejemplo: La siguiente gramtica nos sirve para determinar una oracin EL | La | Lo | Las | Los | Un | Una | Uno |Unas Caballo | Elefantes | Cacahuates | Rosales Blanco | Morado | Verde | Bonito | Feo Come | Corre | Vuela | Salta | Nota : la flecha indica produce de aqu el nombre de producciones es el smbolo vaco .

3.2 rboles de derivacinExisten bsicamente dos formas de describir cmo en una cierta gramtica una cadena puede ser derivada desde el smbolo inicial. La forma ms simple es listar las cadenas de smbolos consecutivas, comenzando por el smbolo inicial y _____________________________________________________________________ I.S.C. Elda Rivera Saucedo 45

Teora de la Computacin finalizando con la cadena y las reglas que han sido aplicadas. Si introducimos estrategias como reemplazar siempre el no terminal de ms a la izquierda primero, entonces la lista de reglas aplicadas es suficiente. A esto se le llama derivacin por la izquierda. Por ejemplo, si tomamos la siguiente gramtica: : (1) S S + S : (2) S 1 y la cadena 1 + 1 + 1, su derivacin a la izquierda est en la lista [ (1), (1), (2), (2), (2) ]. Anlogamente, la derivacin por la derecha se define como la lista que obtenemos si siempre reemplazamos primero el no terminal de ms a la derecha. En ese caso, la lista de reglas aplicadas para la derivacin de la cadena con la gramtica anterior sera la [ (1), (2), (1), (2), (2)]. La distincin entre derivacin por la izquierda y por la derecha es importante porque en la mayora de analizadores la transformacin de la entrada es definida dando una parte de cdigo para cada produccin que es ejecutada cuando la regla es aplicada. De modo que es importante saber qu derivacin aplica el analizador, por que determina el orden en el que el cdigo ser ejecutado. Una derivacin tambin puede ser expresada mediante una estructura jerrquica sobre la cadena que est siendo derivada. Por ejemplo, la estructura de la derivacin a la izquierda de la cadena 1 + 1 + 1 con la gramtica anterior sera: :SS+S (1) :SS+S+S (1) :S1+S+S (2) :S1+1+S (2) :S1+1+1 (2) : { { { 1 }S + { 1 }S }S + { 1 }S } S donde { }S indica la subcadena reconocida como perteneciente a S. Esta jerarqua tambin se puede representar mediante un rbol sintctico:


46


s s s +1

+ s1

s1

La derivacin por la derecha: :S S + S (1) :S 1 + S (2) :S 1 + S + S (1) :S 1 + 1 + S (2) :S 1 + 1 + 1 (2) define el siguiente rbol sintctico:

s s1

+ s1

s + s1

Si para una cadena del lenguaje de una gramtica hay ms de un rbol posible, entonces se dice que la gramtica es ambigua Normalmente estas gramticas son ms difciles de analizar por que el analizador no puede decidir siempre que produccin aplicar. 3.3 Formas normales de Chomsky. _____________________________________________________________________ I.S.C. Elda Rivera Saucedo 47

Teora de la Computacin En lingstica la jerarqua de Chomsky es una clasificacin jerrquica de distintos tipos de gramticas formales que generan lenguajes formales. Esta jerarqua fue descrita por Noam Chomsky en 1956.

La Jerarqua de Chomsky consta de cuatro niveles:

Gramticas de tipo 0 (sin restricciones), que incluye a todas las gramticas formales. Estas gramticas generan todos los lenguajes capaces de ser reconocidos por una mquina de Turing. Los lenguajes son conocidos como lenguajes recursivamente enumerables. Ntese que esta categora es diferente de la de los lenguajes recursivos, cuya decisin puede ser realizada por una mquina de Turing que se detenga. Gramticas de tipo 1 (gramticas sensibles al contexto) generan los lenguajes sensibles al contexto. Estas gramticas tienen reglas de la forma con A un no terminal y , y cadenas de terminales y no terminales. Las cadenas y pueden ser vacas, pero no puede serlo. La regla est permitida si S no aparece en la parte derecha de ninguna regla. Los lenguajes descritos por estas gramticas son exactamente todos aquellos lenguajes reconocidos por una mquina de Turing no determinista cuya cinta de memoria est acotada por un cierto nmero entero de veces sobre la longitud de entrada. Gramticas de tipo 2 (gramticas libres del contexto) generan los lenguajes independientes del contexto. Las reglas son de la forma con A un no terminal y una cadena de terminales y no terminales. Estos lenguajes son aquellos que pueden ser reconocidos por un autmata con pila. Gramticas de tipo 3 (gramticas regulares) generan los lenguajes regulares. Estas gramticas se restringen a aquellas reglas que tienen en la parte izquierda un no terminal, y en la parte derecha un solo terminal, posiblemente seguido de un no terminal. La regla tambin est permitida si S no aparece en la parte derecha de ninguna regla. Estos lenguajes son aquellos que pueden ser aceptados por un autmata finito. Tambin esta familia de lenguajes pueden ser obtenidas por medio de expresiones regulares.

Ntese que el conjunto de gramticas correspondiente a los lenguajes recursivos no es un miembro de la jerarqua. Cada lenguaje regular es a su vez libre del contexto, asimismo un lenguaje libre del contexto es tambin dependiente del contexto, ste es recursivo y a su vez, _____________________________________________________________________ I.S.C. Elda Rivera Saucedo 48

Teora de la Computacin recursivamente enumerable. Las inclusiones son, sin embargo, propias, es decir, existen en cada nivel lenguajes que no estn en niveles anteriores.

Tip o

Lenguaje

Autmata

Normas de produccin de gramticas

0

recursivamente enumerable (LRE)

Mquina de Turing (MT) Autmata linealmente acotado

Sin restricciones

1

dependiente del contexto (LSC)

A

2

independiente del contexto (LLC)

Autmata con pila

A

3

regular (RL)

Autmata finito

A aB Aa

Lenguajes Recursivamente Enumerables (de tipo 0) Artculo principal: Lenguaje recursivamente enumerable Las gramticas que generan estos lenguajes pueden tener reglas compresoras. Las reglas de produccin son de la siguiente forma:

Lenguajes Dependientes del Contexto (sensibles al contexto, de tipo 1) No existen reglas compresoras, salvo, opcionalmente, la que deriva el axioma a la palabra vaca. Existen reglas en las que un smbolo no terminal puede derivar a formas sentenciales distintas, segn los smbolos que aparezcan a su alrededor _____________________________________________________________________ I.S.C. Elda Rivera Saucedo 49

Teora de la Computacin Las reglas de produccin son de la siguiente forma:

Lenguajes Independientes del Contexto (de contexto libre, de tipo 2) La mayora de los lenguajes de programacin entran en sta categora. Las reglas de produccin son de la siguiente manera:

Lenguajes Regulares (de tipo 3) Artculo principal: lenguaje regular Son los lenguajes ms simples dentro la Jerarqua de Chomsky. Se suelen expresar mediante expresiones regulares. Existen 2 tipos: lineales por la derecha y lineales por la izquierda. Las reglas de produccin son de la siguiente forma: Lineales por la derecha:

Lineales por la izquierda:

Jerarquia de Chomsky Segn Chomsky se clasifica las gramticas en cuatro tipos (cuales son, como vemos ms adelante, entre si verdaderamente diferentes).

Entonces sea una gramtica (y ). Las gramticas se distinguen solamente en el sistema de producciones que siempre ser un conjunto finito y que se clasifica en los siguientes tipos: Tipo 0: _____________________________________________________________________ I.S.C. Elda Rivera Saucedo 50

Teora de la Computacin Gramticas generales sin restricciones

es decir, se sustituye por lo menos un smbolo no-terminal. Tipo 1: Gramticas sensibles al contexto

es decir, se sustituye un smbolo no-terminal por algo manteniendo el contexto; entonces una derivacin siempre produce palabras ms largas o iguales ( Tipo 2: Gramticas libres de contexto )

Es decir, se sustituye solo smbolos no-terminales por palabras no vacas Tipo 3: Gramticas regulares (o lineales)

Es decir, lineales a la izquierda (porque los smbolos no-terminales aparecen en una derivacin siempre a la izquierda de la palabra)

Es decir, lineales a la derecha (porque los smbolos no-terminales aparecen en una derivacin siempre a la derecha de la palabra) Se ha introducido explcitamente la regla en las gramticas de

tipos 1, 2, y 3 para permitir que el lenguaje puede ser generado dado que las reglas solo permiten un crecimiento de la longitud de las palabras a lo largo de las derivaciones. Retomamos la clasificacin de las gramticas hacia final del curso (por ejemplo, respondemos a la pregunta si son de verdad clases separadas).


51

Teora de la Computacin Observacin: si permitimos para las gramticas de libre contexto reglas del tipo , es decir, permitimos reglas como , podemos sustituir todas las reglas que tengan una a la derecha, por ejemplo por las producciones compresoras. , y conseguir as una eliminacin de

Jerarqua de Chomsky En funcin de la forma de sus producciones, se puede caracterizar qu tan compleja es una gramtica formal. Noam Chomsky mostr que esta caracterizacin clasifica jerrquicamente a las gramticas formales: Gramticas en un nivel estn incluidas en los siguientes niveles y la inclusin entre niveles es propia. Se puede dar varios refinamientos de la Jerarqua de Chomsky. En la tabla (4) presentamos esquemticamente uno de tales refinamientos. Table 4: Jerarqua gramatical de Chomsky. Tipo 0 Nombres Irrestricta Irrestricta con memoria limitada 1 existe una funcin (computable) tal que la longitud de cualquier cadena en una derivacin que d una palabra ha de estar acotada por el valor de la funcin en la longitud de , Forma de producciones

2

Sensibles al contexto con borro Sensibles al contexto no reductivas , ,

3


52

Teora de la Computacin Libres de contexto Libres de contexto determinis tas producciones libres de contexto con la particularidad de que una vez que se ha derivado prefijos de un cierto tamao entonces se tendr determinada la palabra a derivarse,

4

5

6 7

Lineales Regulares

la tipologa empleada denota lo siguiente: cadenas de Negritas caracteres; MAYSCULAS smbolos variables;

A T V

alfabeto, , conjunto de smbolos terminales, conjunto de smbolos variables.

Lo esquemtico de esta tabla se suprimir en el captulo 3 de este curso, en el que se presentar estas gramticas con todo detalle. En toda gramtica formal aparecen dos problemas fundamentales:

Problema de la palabra: Instancia: _____________________________________________________________________ I.S.C. Elda Rivera Saucedo 53

Teora de la Computacin Solucin:

Es decir, este problema consiste en decidir, para una gramtica y una palabra dadas, si acaso la palabra est generada por la gramtica. Problema de la derivacin: Instancia: Solucin:

Es decir, este problema consiste en encontrar, cuando exista, una derivacin, en una gramtica dada, de una palabra dada tambin. Los problemas mencionados pueden ser resueltos efectivamente en algunos niveles de la Jerarqua de Chomsky. En otros niveles superiores puede ser irresolubles estos problemas.

3.4 Forma Normal de Greibach


54

Teora de la Computacin Def.- Una GLC (gramatica Libre de Contexto)est en Forma Normal de Greibach (FNG) si todas las producciones son de la forma Aa, donde a es un smbolo terminal y ( N)*.

Una gramtica en FNG no puede tener producciones recursivas por la izquierda. Por la forma de las producciones, una gramtica en FNG slo puede generar lenguajes no vacos que no contengan la .

Transformando a Forma Normal de Greibach Es posible transformar cualquier GLC que no contenga la a FNG en varias etapas. Sea L un LLC no vaco, que no contiene la . Sea G=(,N,S,P) una GIC en Forma Normal de Chomsky que genera L. Supongamos que N={A 1 ,A 2 ,...,A n }, donde A 1 =S. Modificamos las producciones de forma que A r A s , es una produccin, entonces r

Documents

Antologias Teoria de La Computacion