Licenciatura en Ingeniera en Sistemas Computacionales

Antologa de la Asignatura de Compiladores

Autor 5to Sistema

Presentacin

El objetivo de esta antologa es que los alumnos de 5to de Sistemas adquieran el conocimiento necesario para comprender como trabaja el analizador lxico dentro de la funcin de los compiladores. Los principios y tcnicas de escritura de compiladores son tan amplios que las ideas encontradas se usaran muchas veces en la carrera de un ingeniero en sistemas. La escritura de compiladores comprende los lenguajes de programacin, la arquitectura de computadoras, la teora de lenguajes, los algoritmos y la ingeniera de software. Con los compiladores se pueden construir traductores para una gran variedad de lenguajes y maquinas. La elaboracin de esta antologa es para que los alumnos desarrollen a lo largo de su vida estudiantil y profesional el comprender el anlisis lineal (anlisis lxico), y sus componentes. Identificador de posicin Smbolo de Asignacin Identificador inicial Signo de suma Identificador velocidad Signo de multiplicacin El numero 60

Sugerencias

Analizador Lxico

El principal objetivo del analizador lxico es leer el flujo de caracteres de entrada y transformarlo en una secuencia de componentes lxicos que utilizar el analizador sintctico.Al tiempo que realiza esta funcin, el analizador lxico se ocupa de ciertas labores de limpieza". Entre ellas est eliminar los blancos o los comentarios. Tambin se ocupa de los problemas que pueden surgir por los distintos juegos de caracteres o si el lenguaje no distingue maysculas y minsculas.Para reducir la complejidad, los posibles smbolos se agrupan en lo que llamaremos categoras lxicas. Tendremos que especificar qu elementos componen estas categoras, para lo que emplearemos expresiones regulares. Tambin ser necesario determinar si una cadena pertenece o no a una categora, lo que se puede hacer eficientemente mediante autmatas de estados finitos.Las unidades lgicas que genera el analizador Lxico se denominan tokens, y formar caracteres en tokens es muy parecido a formar palabras a partir de caracteres con una oracin en un lenguaje natural como el ingls o cualquier otro y decidir lo que cada palabra significa.

UNIDAD I: ANALIZADOR LEXICO

Funcin Principal Leer carcter por carcter de la entrada y elaborar como salida una secuencia de componentes lxicos (tokens) que utiliza el analizador sintctico para hacer el anlisis.Funciones secundarias Manejar el archivo fuente, es decir, abrirlo, leer sus caracteres y cerrarlo. Eliminar comentarios y espacios en blanco (espacios, tabuladores y fin de lnea). Relacionar los mensajes de error con las lneas del programa fuente. Introducir los identificadores en la tabla de smbolos.

Razones para dividir en dos fases Diseo ms sencillo: los smbolos que trata el analizador lxico se describen con una gramtica ms simple (gramtica regular) que la del analizador sintctico (gramtica libre de contexto). Mejora la eficiencia: gran parte del tiempo de compilacin se consume en la lectura y exploracin de caracteres. Con tcnicas especializadas de manejo de buffers se puede mejorar significativamente el rendimiento del compilador. Mejora la portabilidad: se pueden tener varias versiones del analizador lxico una para distintos cdigos (EBCDID, ASCII...), con el mismo analizador sintctico.

Token, patrones y lexemas.Token (componente lxico): es un par que consiste en un nombre de token y un valor de atributo opcional. Patrn: el conjunto de cadenas de la entrada se describe mediante una regla llamada patrn asociada al componente lxico. Un patrn es una regla que describe el conjunto de lexemas. Para describir los patrones se utiliza la notacin de expresiones regulares. Lexema: secuencia de caracteres en el programa fuente con lo que concuerda el patrn para un token. Los lexemas para el token que concuerdan con el patrn representan cadenas de caracteres en el programa fuente que se pueden tratar como unidad lxica.

Atributos para los tokensCuando una secuencia de caracteres (por ejemplo, pi) aparece en el programa fuente se devuelve al analizador sintctico un token que representa un identificador. Pero es necesario que el analizador lxico proporcione informacin adicional sobre el lexema concreto. Esta informacin adicional se denomina Atributos. Por ejemplo, el patrn nmero concuerda con las cadenas 3.1416 y 0, pero es indispensable que el generador de cdigo conozca que cadena fue realmente la que se emparejo. El analizador lxico recoge informacin sobre los tokens en sus atributos asociados. El nombre de un token influye en las decisiones del analizador sintctico, y el valor del atributo, en la traduccin de los tokens despus del analizador sintctico. En la prctica los tokens suelen tener un solo atributo, un puntero a la tabla de smbolos, donde se guarda informacin del token. El puntero se convierte en el atributo. No siempre se necesita un valor de atributo, el nombre del token es suficiente para identificar al lexema.

Especificacin y reconocimiento de los tokens.Dos cuestiones: Cmo especificar los tokens? Cmo reconocer los tokens? Especificacin Todos los elementos bsicos en un lenguaje deben ser tokens, por lo tanto deben reconocerse. Los tokens se especifican con Expresiones Regulares

Reconocimiento de tokens.Como paso intermedio en la construccin de un Analizador Lxico se produce un diagrama de transicin. Estos diagramas representan acciones que el analizador lxico debe llevar a cabo para obtener el siguiente token. Acciones: Getchar: leer el siguiente carcter de entrada. Devuelve (nombre-token, atributo): luego de reconocer un token, el A.L. devuelve al Analizador Sintctico el token y el atributo. con asterisco se indica que se debe retroceder el puntero de entrada un smbolo a la izquierda.

Errores lxicos.Hay pocos errores que el analizador lxico puede detectar ya que tiene una visin muy restringida de un programa fuente. Estrategias de recuperacin Modo de pnico. Eliminar un carcter del resto de la entrada. Sustituir un carcter por otro. Transponer dos caracteres adyacentes

ACTIVIDAD 1

1.- Cul es la funcin principal del analizador lxico?

2.- Qu funciones secundarias tiene el analizador lxico?

3.- Cules son La razones de dividir en dos fases el analizador?

4.- Describe un token, patrn y lexema

5.- Qu atributos tienen los tokens?

6.- Cules son las especificaciones de los tokens?

7.- Cmo se reconoce un token?

8.- Qu errores lxicos existen?

UNIDAD II: EL PROCESO DEL ANALISIS LEXICO

El trabajo del analizador lxico es leer los caracteres del cdigo fuente y formarlos en unidades lgicas. Las unidades lgicas que genera el analizador lxico se denominan tokens.Para hacer clara la distincin, la cadena de caracteres representada por un token se denomina en ocasiones su valor de cadena o su lexema. No obstante un token puede representar un nmero infinito de lexemas. Un rastreador o analizador lxico tambin debe construir los valores de cadena de por lo menos algunos tokens.El analizador lxico posiblemente tendr que calcular varios atributos para cada token, a menudo es til recolectar todos los atributos en un solo tipo de datos estructurados, al que podramos denominar como registro de token.EXPRESIONES REGULARESRepresentan patrones de cadenas de caracteres. Una expresin regular r se encuentra completamente definida mediante el conjunto de cadenas con las que concuerda. Este conjunto se denomina lenguaje generado por la expresin regular y se escribe como L(r). En general, estaremos hablando del conjunto de caracteres ASCII, en cuyo caso los elementos del conjunto se describirn como smbolos. Este conjunto de smbolos legales se conoce como alfabeto y por lo general se representa mediante el smbolo griego (sigma).Una expresin regular r puede contener caracteres que tengan significados especiales. Este tipo de caracteres se llaman meta caracteres o meta smbolos, y por lo general no pueden ser caracteres legales en el alfabeto, porque no podramos distinguir su uso como meta caracteres de su uso como miembros del alfabeto.Expresiones regulares bsicas Estn son precisamente los caracteres simples del alfabeto, los cuales se corresponden a s mismos. Necesitamos poder indicar una concordancia con la cadena vaca, es decir, la cadena que no contiene ningn carcter.Operaciones de expresiones regulares, existen tres operaciones bsicas en las expresiones regulare: 1) seleccin entre alternativas, la cual se indica mediante meta carcter 2) concatenacin, que se indica mediante yuxtaposicin3) repeticin o cerradura, la cual se indica mediante meta carcter.En los siguientes prrafos describimos algunas extensiones de las expresiones estndares ya analizadas.

UNO O MAS REPETICIONESDada una expresin regular r; la repeticin regular de r se describe utilizando las expresiones de cerradura estndar. Esto permite que repita 0 o ms veces.CUALQUIER CARCTERSin una expresin especial esto requiere que todo carcter el alfabeto sea enumerado en una alternativa. Con el meta carcter se utiliza para expresar una concordancia es el. (Punto) podemos escribir cualquier letra. .*b.*.UN INTERVALO DE CARACTERESUna alternativa es tener una notacin especial para esta situacin, y una que es comn es usar CUALQUIER CARCTER QUE NO ESTE EN UN CONJUNTO DADOEste se puede conseguir al disear un meta carcter para indicarla operacin de negacin (not) o complementario para un conjunto de alternativas.SUBEXPRESIONES OPCIONALES Un seceso que se presenta comnmente es el de cadenas que contienen partes opcionales que pueden o no aparecer en cualquier cada en particular.[footnoteRef:1] [1: ]

ACTIVIDAD 2Resuelve la siguiente sopa de letras.

1. 2. REGISTRO DE TOKENS3. PROCESO DE ANALIZADOR LEXICO4. EXPRESIONES REGULARES5. METAS CARACTERES 6. TOKENS7. INTERVALO DE CARACTERES8. SELECCIN ENTRE ALTERNATIVAS9. CONCATENACION10. CERRADURATOVDSOOKNTOKREGOPKZWXAEGUVXMET

UUNOOMASREPETICIONESAURNJPFQRS

ENNRTEGKEPCOYSENOEZHNPJKPPRPZV

SAORETPTGEBTMXNPQXZIMWXCRROXCA

ALRPEAZTETAREEOCTANMOEABBOOCXJ

VPTBSGXOSINBRFTCTQWGFUTUNCPCEW

IOEYGCITTCENMSERETCARACATEMQEZ

TTORSPTSRIMRDMUANSELGHSMCSMOAS

AANAOZQOTOLKSRPEREIPZEBHJOOPWT

NNNEAOZMORROSAUXRSPEROHSJDDPAS

RAOEZLANALOPZADPSBZYRGEEOEMEWB

EALWRUILNUCDBIKODAXPNRERAAGATT

TBQTRTRJONOUEJBGOAXLATUEBNCENO

LCSAERLHQOLCNTMSVSQLSNNTOARCHX

ADCNOICANETACNOCIFUBOINCLTOIC

EFELENMEEOMABVJKRGNOMOFAOIAYQO

RERIDKANURAQERZIEMNMOBERKZIOIN

TRRZNCOTIMTCIXRRBNOASSQAJALAIL

NTRAOOCTEACSIOSFASDUTRRCHDEAA

EOADINILCSVITEAECECNALTEGONQAZ

NKDOECOKINAFNOVDELAPDLYDDRFTMS

ONCRLANNNICODCAADEXQEEUOSLWEEA

IDBLPALSEGIBOEDJOCTOSSJLNEQWTD

CSVEOTEASSIARRFELIALHOIAOXRQTB

CEPGYCXEEAOCSRRXVOVGNOVPITEAY

ESLAHIWFSSLCRATPTARUDARRECXFCL

LPBJOSOCREORDNEREEMGINEJOYICE

EEWKMXACCTXMGSHSTNTLBJMTKCHYAX

SSSEEKOOOAIOEATINTLPNIKNINMRT

XAEXPEESTSIBRNGIIRAAMJLINOBNEF

11. UNO O MAS REPETICIONESUNIDAD III Tokens

Son las palabras reservadas de un lenguaje, secuencia de caracteres que representa una unidad de informacin en el programa fuente. En cada caso un token representa un cierto patrn de caracteres que el analizador lxico reconoce, o ajusta desde el inicio de los caracteres de entrada. De tal manera es necesario generar un mecanismo computacional que nos permita identificar el patrn de transicin entre los caracteres de entrada, generando tokens, que posteriormente sern clasificados. Este mecanismo es posible crearlo a partir de un tipo especfico de mquina de estados llamado autmata finito. Varias cadenas diferentes en la entrada pueden dar el mismo token a la salida, un token se describe mediante un patrn en la mayora de los son tokens:

Palabras clave, operadores, identificadores, constantes, cadenas literales y signos de puntacin Existen una serie de palabras clave (reservadas) en muchos lenguajes que conviene introducir directamente en la tabla de smbolos:Tokens Lexemas

if If

id x1,a,b

relacin >

op +

asign :=

then Then

num 3

Componentes lxicos (Tokens).Son las unidades lgicas que genera el analizador lxico. Es el conjunto de cadenas de entrada que produce como salida el mismo componente lxico. Cada token es una secuencia de caracteres que representa una unidad de informacin en el programa fuente.

Los componentes lxicos ms comunes son los siguientes: palabras clave o reservadas operadores aritmticos operadores relacionales operadores lgicos operador de asignacin identificadores constantes cadenas literales signos de puntuacin librerasPara los tokens id y nm. es necesario recoger el lexema para poder despus realizar comprobaciones semnticas (por eje: declaracin antes de uso). El lexema de los componentes lxicos se almacena en el campo lexema de la estructura. Por comodidad se ha almacenado para todos los tipos de tokens.

ACTIVIDAD 3

De la siguiente sopa de letra buscar las 11 palabras escondidas. 1.-cadenas 6.-Literales 11.-Automata finito2.- tokens 7.-Operadores Lgicos3.- identificadores 8.-Palabra Clave4.-Palabra Clave 9.-Lexemas5.-Libreria 10.-Componentes lxicos

AQWRTYAFGHJKLXVBQSHJ

UIECDYBMESGFOLKJEWC

TJHAWYOSDKOJPQERHREV

OKTDKGIPNJPKEWUYGORB

MLLEXEMASRDLROPGFDTN

AWGNPOILITERALESDAYM

TQFAHCATOMNDOIFSCUQ

ATESRQVBRKBOLPGAIIW

FYRTQSBRFELVRWQRPFOE

IUDCWIQADNJCEADGOIPR

NICVTUECQSHXSJWPITAT

IABBYRRLDFGZLIQLUNSY

TWQSSTWAFGHJOWWYEDU

OJKIUYQVRRWQGSAERDFI

GHJKJTFEHJKLIBRERIAO

VSEWGHSRTNHICLCPOIDA

KTURWRKHOBVCOTKPUFS

QWERTYUIQWDGSPEDLYGD

EVALCARBALAPTOROKTHF

GQWEOPFGTZUIRITKHRJG

JFROJWKESCROEUYHGEKH

FWGHSCVBNXEPDUGFWLJ

EQWETUIPBVDQHLIVDQOK

RCOMPONENTESLEXICOSL

UNIDAD IV: Autmatas Finitos (AF)Hay varias razones por las que el estudio de los autmatas y de la complejidad es una parte importante del ncleo de las ciencias de la computacin. Los AF constituyen un modelo til para muchos tipos importantes de hardware y software, como:a) Software para el diseo y la verificacin del comportamiento de circuitos digitales.b) El analizador lxico de un compilador tpico, esto es, la componente del compilador que descompone el texto original en unidades lgicas tales como identificadores, palabras reservadas y signos de puntuacin.c) Software para explorar grandes corpus de texto, como conjuntos de pginas web, o para descubrir las apariciones de ciertas palabras, frases u otros patrones.d) Software para comprobar la correccin de cualquier tipo de sistemas que tengan unNmero finito de estados diferentes, como los protocolos de comunicacin o los protocolos de intercambio seguro de informacin.Hay muchos sistemas o componentes, como los enumerados anteriormente, de los que se puede decir en todo momento que estn en cierto estado, entre un nmero finito de ellos. El objetivo de un estado es recordar la parte significativa de la historia del sistema. Dado que solo disponemos de un nmero finito de estados, normalmente no es posible recordar la historia completa, por lo que el sistema ha de ser diseado cuidadosamente para que sea posible recordar los aspectos importantes y olvidar los que no lo sean.Definicin informalUn AF es una mquina reconocedora, ya que a partir de una cadena de entrada, solo dice si o no. Lo cual indica si esa cadena pertenece o no al lenguaje reconocido o aceptado por laMquina. A partir de una gramtica se puede construir una mquina reconocedora o aceptadora del Lenguaje generado por esa gramtica, de tal forma que cuando reciba a su entrada una determinada cadena de smbolos, el autmata indicar si dicha cadena pertenece o no al lenguaje. Una mquina reconoce un lenguaje L si es capaz de reconocer todas las sentencias pertenecientes a L y de no reconocer ninguna sentencia que no pertenezca a L. Los lenguajes regulares pueden describirse por medio de un AF.Un AF tiene un conjunto de estados y su control se mueve de estado en estado, en respuesta a entradas externas. Estas entradas forman las cadenas a ser analizadas. Los estados de un AF, son de tres tipos: estado inicial, que permite empezar la ejecucin del autmata; estados finales o estados de aceptacin que permiten realizar la salida de aceptacin de la cadena de entrada en el caso de que no haya ms smbolos en la entrada, y estados intermedios, que son los que permiten pasar del estado inicial a algn estado final.Los AF se dividen en diversas clases, dependiendo de si su control es determinista (lo que significa que el autmata no puede estar en ms de un estado simultneamente) o no determinista (lo que significa que el autmata puede estar en varios estados al mismo tiempo)

Autmatas Finitos Deterministas

El autmata finito determinista (AFD) siempre est en un solo estado despus de leer cualquier secuencia de entrada. El trmino determinista hace referencia al hecho de que, para cada entrada, existe un nico estado al que el autmata pueda llegar partiendo del estado actual.Un AFD se denota con la quntupla: A = (_, Q, f, q0, F) donde: _ es el alfabeto (conjunto finito) de smbolos de entrada. Q es el conjunto finito de estados. q0 Q es el estado inicial. f, es la funcin de transicin, es una funcin que toma como argumentos un estado de Q y un smbolo de entrada de _ y devuelve un estado. F Q, es el conjunto de estados finales (o de aceptacin).Como ya se ha comentado, un AFD genera un solo tipo de salida: acepta o no una secuencia de smbolos de entrada. Esa aceptacin est representada si el autmata se encuentra en algn estado del conjunto F.El comportamiento de un AFD, comienza en el estado inicial (q0), y segn se van recibiendo los smbolos de la entrada transita entre los estados (del conjunto Q), de acuerdo a la funcin de transicin f. Si en un determinado momento se encuentra en un estado de aceptacin (del conjunto F), reconoce como vlida la cadena formada por los smbolos de entrada ledos hasta el momento. Si no, no es aceptada.EjemplosEjemplo 1: El autmata que acepta, cadenas de 0 y 1 con un nmero par de unos (y no acepta cadenas con un nmero impar de unos), es el siguiente:A1 = ({0,1}, {q0, q1}, f, q0, {q0})Donde f, se define como:f(q0,0) = q0f(q0,1) = q1f(q1,0) = q1f(q1,1) = q0Si la cadena de entrada es 0110, el autmata ir transitando entre los estados:0 1 1 0q0 _ q0 _ q1 _ q0 _ q0Ejemplo 2: En este ejemplo, partiremos de un Lenguaje L y encontraremos el AFD, que reconoce este lenguaje.

Representaciones de un AFDLa especificacin de un AFD como una quntupla, con una descripcin detallada de la funcin de transicin f, es tediosa y difcil de leer. Existen dos notaciones preferibles para describir los autmatas:1. Un diagrama de transiciones, que es un grafo.2. Una tabla de transiciones, que es una enumeracin tabular (tabla) de la funcin f, que a la vez describe el conjunto de estados, y el alfabeto de entrada.

Diagramas de transicionesUn diagrama de transiciones para un AFD A = (_, Q, q0, f, F), es un grafo definido de la Siguiente forma:a) Hay un nodo para cada estado de Q.b) El nodo correspondiente al estado inicial q0, tendr una flecha sin origen (o arco entrante) no etiquetado.c) Los nodos correspondientes a los estados de aceptacin (los que pertenecen a F) estn marcados con un doble crculo. Los que no pertenecen a F tienen un crculo simple.d) Habr un arco etiquetado con a entre el nodo p y el nodo q, si f(p,a) = q. Si existen varios smbolos de entrada que provocan una transicin del estado p a q, entonces el arco entre p y q quede estar etiquetado con la lista de esos smbolos.

Ejemplo 1: Autmata para aceptar el lenguaje de cadenas de 0 y 1, con cantidades de 1 pares

Tabla de transicionesUna tabla de transiciones es una representacin tabular convencional de una funcin como f, que recibe dos argumentos y devuelve un valor. Esta tabla tendr las siguientes Caractersticas:a) En las filas estarn los estados q Qb) El estado inicial se preceder del smbolo ->c) Cada estado final se preceder del smbolo *d) En las columnas estarn los smbolos de entrada a _e) El valor correspondiente a la fila del estado q y a la entrada a es el estado que determine f(q,a)

Autmatas Finitos no Deterministas (AFN)

Un autmata finito no determinista AFN tiene la capacidad de estar en varios estados simultneamente. La diferencia entre AFD y un AFN est en la funcin de transicin. Para el AFN, f es una funcin que toma como argumentos un estado y un smbolo de entrada, pero devuelve un conjunto de cero, uno o ms estados (en vez de devolver un estado, como en el caso del AFD).

Un AFN se representa, esencialmente, como un AFD:A = (_, Q, q0, f, F) donde: _ es el alfabeto (conjunto finito) de smbolos de entrada. Q es el conjunto finito de estados. Q0 Q es el estado inicial. F, es la funcin de transicin, es una funcin que toma como argumentos un estado de Q y un smbolo de entrada de _ y devuelve un subconjunto de Q.f : Q x _ -> P(Q) conjunto de estados F Q, es el conjunto de estados finales (o de aceptacin).

La funcin de transicin extendidaAl igual que para los AFD, tenemos que extender la funcin de transicin f de un AFN a una funcin f que tome como argumentos en estado q y una cadena de smbolos de entrada w, y devuelva el conjunto de estados en los que estar el AFN si comienza en el estado q y procesa la cadena w.0,10 1q0 q1 q2Para poder entender esta funcin primero, veremos cmo funciona un AFN para el reconocimiento de una cadena. Mientras que en un AFD de cada estado sale un arco para cada smbolo de entrada, un AFN no tiene esta restriccin: vemos en el ejemplo anterior casos en que el nmero de arcos es cero, uno o dos para cada smbolo de entrada.

Lenguaje de un AFNComo se ha sugerido, un AFN acepta una cadena w si, a medida que se leen los caracteres de w, es posible elegir en cada paso el estado siguiente, de tal forma que se pase desde el estado inicial a un estado de aceptacin. El hecho de que existan otras elecciones posibles que, siguiendo los smbolos de w, lleven a un estado que no es de aceptacin o no lleven a ningn estado (es decir, el hecho de que la secuencia de estados muera), no evita que w sea aceptada por el AFN en su conjunto. Formalmente, si A = (_, Q, f, q0, F) es un AFN, , entonces L(A) = {w / f (q0,w) _ F _ .Es decir, L(A) es el conjunto de cadenas w pertenecientes a _* tales que f (q0,w) contiene al menos un estado de aceptacin.

Equivalencia entre autmatas Finitos Deterministas y No deterministasEs un hecho sorprendente que todo lenguaje que puede describirse mediante un AFN tambin puede describirse con un AFD. Ms an, en la prctica, el AFD tiene casi el mismo nmero de estados que un AFN, aunque a menudo tiene ms transiciones.La demostracin de que un AFD puede hacer lo mismo que un AFN implica una construccin importante, llamada construccin de subconjuntos, porque supone construir todos los subconjuntos del conjunto de estados del AFN. En general, muchas demostraciones sobre autmatas obligan a construir un autmata a partir de otro. Es importante fijarse en la construccin de subconjuntos como ejemplo de cmo se puede describir formalmente un autmata en funcin de los estados y transiciones de otro sin conocer los detalles especficos del segundo.La construccin de subconjuntos parte de un AFN N =(_, QN, fN, q0, FN). Su objetivo es la descripcin de un AFD D =(_, QD, fD, {q0}, FD) tal que L(D) = L(N). Ntese que los alfabetos de entrada de ambos autmatas son idnticos, y el estado inicial de D es el conjunto que contiene solo el estado inicial de N. Las otras componentes de D se construyen de la siguiente forma: QD es el conjunto de subconjuntos de QN; es decir, QD es el conjunto potencia de QN. En la prctica vemos que pueden existir estados inaccesibles desde el estado inicial y por lo tanto son eliminados... Es decir, FD todos los conjuntos de estados de N que incluyen al menos un estado

Autmatas Finitos con transiciones

Vamos a presentar otra extensin de los autmatas finitos. Como nueva caracterstica,Permitiremos transiciones para _ ( _), la cadena vaca. Con ellas, un AFN puede hacer transiciones espontneamente sin recibir ningn smbolo de entrada. Igual que como sucedi cuando aadimos el no determinismo a los autmatas, esta nueva capacidad de los autmatas tampoco expande la clase de lenguajes que aceptan los autmatas finitos, pero proporcionan algunas facilidades de programacin.Se puede representar a un AFN-_ exactamente igual que un AFN, con una sola excepcin: la funcin de transicin debe incluir informacin sobre las transiciones _. Formalmente, representaremos a un AFN-_ A mediante A = (_, QN, f, q0, F), donde todas las componentes tienen la misma interpretacin que en un AFN, excepto que f es ahora una funcin, cuyos argumentos son:1. Un estado perteneciente a Q.2. Un miembro de _{ _ }, es decir, un smbolo de entrada o el smbolo _. Se exige que _, el smbolo que representa la cadena vaca, no forme parte del alfabeto _, para que no se produzcan confusiones.

Ejemplo: El siguiente autmata AFN-_ acepta nmeros decimales que contienen:1. un signo + o - opcional2. una cadena de dgitos3. un punto decimal4. otra cadena de dgitos

ACTIVIDAD 4

El software en que es til en autmatas finitos? Para el diseo y la verificacin del comportamiento de circuitos digitales.

Qu es un AF?Es una mquina reconocedora, ya que a partir de una cadena de entrada, solo dice si o no.

Cules son los tres tipos de estados de los AF?Estado inicialEstados finales o estados de aceptacin Estados intermedios

Cules son clase en que se dividen los AF?deterministano determinista

UNIDAD V: Conversin de una expresin regular a un autmata finito no determinista (NFA)Antes de hacer la conversin propiamente dicha de una expresin regular a un NFA, recordemos la definicin de este tipo de autmata vista en el captulo 1.Un NFA es una 5-tupla (Q Z, 8, q, F) donde: Q es un conjunto finito de estados Z es un alfabeto finito 8: Q xZE ^P (Q) es la funcin de transicin q 0 e Q es el estado inicial f c Q es el conjunto de estados de aceptacin Un ejemplo de un NFA aparece en la Fig. 1.

Ilustracin 1Fig. 1: Un NFA que reconoce a la cadena vaca o cadenas que tienen cualquier nmero de as

Analicemos cada una de las partes de este NFA.1. Q = {qi, q2, qs}2. Z = {a,b}3. Revisemos con detenimiento la funcin de transicinS. Una funcin es un objeto que define una relacin de entrada-salida; i.e., una funcin recibe una cierta entrada y produce una salida especfica. El lado izquierdo de la flecha en la funcin de transicin es la entrada para esa funcin y el lado derecho de la flecha denota la salida. As que la funcin de transicin toma como entrada un par ordenado cuyo primer elemento es un elemento de Q y cuyo segundo elemento es un elemento de Zs (i.e., Z u s). Este conjunto de pares ordenados est definido por el producto cartesiano, representado por Q x Zs, entre el conjunto de estados y el alfabeto (incluida la cadena vaca). As que el producto cartesiano de dos conjuntos, digamos Q y Zs, es el conjunto de todos los pares ordenados cuyo primer elemento pertenece a Q y cuyo segundo elemento pertenece a Zs. Note que el orden de los elementos de un par ordenado, a diferencia del orden de los elementos de un conjunto, s importa, por lo que en general, dados 2 conjuntos A y B, A x B ^ B x A. Ahora bien, la salida de la funcin de transicin es un elemento del conjunto potencia del conjunto de estados. El conjunto potencia de un conjunto A es el conjunto de todos los subconjuntos de A. Para este caso especfico, el conjunto potencia de Q, denotado P(Q) = {0, {qi}, {q2}, {q3}, {qi,q2}, {qi,q3}, {q2,q3}, {qi,q2,q3}}. Con estas definiciones en mano, podemos ya saber cul es la salida de la funcin de transicin para cada par ordenado. Dado el NFA de la Fig. 1, las entradas y salidas correspondientes a dicha funcin las representamos en la Tabla 1: Resultado de la funcin de transicin para el NFA de la Fig. 1Tabla 1ABS

qi0{q2}{q3}

q2{q2,q3}{q3}0

q3{qi}00

Tabla 1: Resultado de la funcin de transicin para el NFA de la Fig. 1

Como se puede observar, el resultado de cualquier combinacin estado-elemento del alfabeto es un conjunto de estados que pertenece al conjunto potencia. Adems, note que el conjunto potencia nos permite representar el no-determinismo: por ejemplo, dado el estado q2 y una entrada a, el NFA nos permite quedarnos en ese estado o ir al estado q3 lo cual lo representamos como el estado combinado {q2,q3}; o bien, el conjunto potencia nos permite representar que no hay transicin definida para el estado q1 y una entrada a, representndola como 0.

4. El estado inicial q0 = q15. El conjunto de estados de aceptacin F = {q1}Para realizar la conversin de una expresin regular a su correspondiente NFA, necesitamos la ayuda de 3 teoremas, los cuales presentamos a continuacin [ref. Sipser].Teorema 1: La clase de lenguajes regulares es cerrada bajo la operacin de unin.Sean A1 y A2 dos lenguajes regulares, queremos probar que A1 uA2 es regular. La idea es tomar dos NFAs, Mx y M2 para A y A, respectivamente, y combinarlos en un nuevo NFA que llamaremos M .La mquina M debe aceptar una estrada si M o M aceptan esa entrada. La nueva mquina tiene una nuevo estado inicial, con una transicin s al estado inicial de M1 y otra transicin s al estado inicial de M. De esta manera la nueva mquina adivina no deterministicamente cul de las dos mquinas acepta dicha entrada. Si una de ellas acepta una entrada M la aceptar tambin.

Representamos esta construccin en la Fig. 2. En la parte superior podemos ver a las dos mquinas M y M, en cada una se encuentran el estado inicial, el o los estados finales (en doble circulo) y algunos estado intermedios. La parte inferior muestra a la mquina M, la cual contiene tanto a Mx como a M2, adems de tener un estado adicional que contiene dos transiciones s , una a M1 y otra a M 2 .

Ilustracin 2Fig. 2: Construccin de un NFA para reconocer A1 u A2

DemostracinSean M1 = (Q1, E, S1, q1, F1) que reconoce a A y M2 = (Q2, E, S2, q2, F2) que reconoce a A2. Construyamos M = (Q, E, S, q0, F) para que reconozca a A u A21. Q = {q