UNIVERBIDAD AUTONOMA METROPOLITANA UNIDAD …

UNIVERBIDAD AUTONOMA METROPOLITANA UNIDAD IZTAPALAPA

REPORTE DEL PROYECTO TERMINAL

ALUMNO : LUIS VILLANUEVA PIMENTEL., c _ - ~ - -

ASESORA : PROFA. GRACIE

,

MARZO DE 1992.

INDICE l. Introducción

Ob j et ivos

Manual Tecnico

Manual de Usuario

Conclusiones

Bibliografía

El presente documento muestra ell-manejo de un paquete didáctico, que fué elaborado en la Universidad Autdnoma Metropolitana de Iztapalapa, esperando ser de utilidad para aquellos alumnos de la Licenciatura en Computación, que cursen la materia de Teoría Matemática de la Computación.

Resulta interesante tratar uno de los temas más sobresalientes de e'sta materia, como es la obtención de un Autómata Finito Deterrninístico (AFD), apartir de una expresión regular tomando en cuenta que está puede ser tan compleja de tal manera que su manejo manual nos llevaría un tiempo considerable para obtener su Autómata.

Es importante hacer notar que para la implementación de este programa se diseñaron todos los algoritmos, utilizando una metodología muy particular, debido a que la mayoría de los autores no contemplan la importancia de estos, más bien se centran en describir aspectos teóricos con ejemplos para este tema.

El texto se divide en cinco partes. En la primera se mencionan los objetivos de éste. La notación formal para el lenguaje utilizado comienza en la segunda parte;la tercera comprende el manual técnico, que contiene: notación,la teoría (definiones y conceptos), ciclo de los Autómatas, desarrollo (lectura de una expresión regular; asignación de prioridades;construcción de AFN con @;construcción del AFN sin @; AFD), resumen tedrico, estructuras de datos y variables globales, procedimientos y algoritmos para obtener un AFD. La tercera parte comprende el manual de usuario que contiene: requerimientos del programa, instalación del mismo, ejecución del programa (elección de algún alfabeto opcional o no opcionaltelección erronea y salida), generación de resultados (por pantalla e impresos) y finalmente ejemplos. En la cuarta parte se hace mención a las conclusiones obtenidas en este proyecto. Y la última parte se refiere a la bibliografía utilizada.

Agradeciendo de antemano al usuario y lector sus valiosas sugerencias a este manual.

OBJETIVOS I La idea primordial de este paquete, como mencionamos

anteriormente, es servir como un material didáctico auxiliar para las personas que de alguna manera esten involucradas con el estudio de la teoría matemática de la computación.

El objetivo principal del presente trabajo, es convertir una expresión regular, en un Autómata Finito Determinístico.

Al recibir como entrada una expresión regular debemos obtener :

a).- El estado inicial del Autómata. b).- Transiciones con l o s símbolos del alfabeto. c).- Estado(s) final(es) del AFD el cual lo representaremos

como una tabla de estados.

I MANUAL TECNICO

Manual Técnico l.

Notación

Teoría . -Definiciones

-Conceptos

Ciclo de los Autómatas

Desarrollo

-I. Lectura de una expresión regular

-11. Asignación de prioridades

-111. Construcción del Autómata Finito Determinístico

(A.F.D.)con @

-1V. Construcción del Autómata Finito Determinístico sin @

-V. Autómata Finito Determinístico (Estados Alcanzables)

Resumen Teórico

Estructuras de Datos y variables globales

Procedimientos y Algoritmos para obtener un A.F.D.

NOTACION

t. """""""_ Alfabeto

@ """""""_ Cadena vacia

Unión

Concatenación

Cerradura de Kleen

+ """""""_ """""""_

* """""""_ ( """""""_ Indice de prioridad en las expresiones

) """""""_ Indice de prioridad en las expresiones

(y """""""_ Infinito

En el programa se tomarón las siguientes convenciones

hablar de + Significa MAS

. significa PUNTO

* significa ASTERISCO

( significa PAR-IZQ

) significa PAR-DER

ALFABETOS VALIDOS

Ceros y unos ( 8 , l }

Digitos ( 0,1,2 ... 9 }

Letras { a,A,b,B,c,C .... z,Z }

Alfanumérico ( 0...9,a,A ... z,Z )

Opcional ( los que el usuario desee ).

representa cualquier edo.

representa un edo. final

I TEORIA I

Definición.- Un Alfabeto C es un conjunto finito de símbolos

c = ( 0,l ) C = ( a,b }

Una cadena es una secuencia finita de simbolos de algún alfabeto.

C = ( 0,l }

0,1,00,001,011,111

C = ( a,b }

a,ab,abb,bba

Todo conjunto finito de palabras (cadenas) sobre X , incluyendo la cadena vacia, es un conjunto regular.

Lonaitud de la cadena

101 = 1 1011 = 2 lOOll= 3 I @ / = o

la1 = 1 lab1 = 2 labbl = 3

Prefijo de la cadena

x = o111 @

O

o1

o11

o111

x = o111

Sufiia de la cadena

@

1

11

111

o111

L.

Sean X,Y cadenas de algún alfabeto

Concatenación de cadenas

X . Y

x = o1

Y = 10 x . Y = 0110

X = A B

Y = B A X . Y = A B B A

La concatenación puede ser asociativa pero no cumple la propiedad de conmutatividad.

Potenciación

x = x x* = x . x x q = x . x . x x . x X" = @

Definición.- Un lenguaje es cualquier conjunto de cadenas formadas con los simbolos de algún alfabeto.

c = { 0,l } = ( a,b }

L = ( O } L = ( a } t.

L = ( 00,ll ) L = { aa,bb }

L = { @ } L = ( @ )

L = ( 1,11 ) L = ( a,aa )

Sean L y M lenguajes

Las tres operaciones básicas que se definen para dos lenguajes son : UNION, CONCATENACION Y CERRADURA DE RLEEN.

1.- unión

L = ( 0,l } M = ( a,b )

L + M = ( x ( x e L ó x e M )

L + M = { O,l,a,b )

2.-Concatenación

L = ( 0 , l ) M = { a,b )

L + M = ( X . Y I X E L ~ Y E M )

L + M = ( Oa,Ob, la,lb )

L = L

L2 = L . L

L q = L . L . L L . L

L" = ( @ I

3.- La cerradura de kleen d un lenguaje L se denota por L* y se define como :

L* = { @,0,1,00,01,10,11,000,001......... )

4 . - Cerradura positiva

L* = L u ( @ )

Por convenci6n la precedencia de las operaciones en orden decreciente es ASTERISCO, PUNTO, MAS..

Una EXPRESION REGULAR r de de un alfabeto C, define un lenguaje que denotaremos L( r) . Las expresiones regulares sobre C y los lenguajes que estas

denotan son:

1.- @ Es la expresión regular que denota al lenguaje vacio. 2.- @ Es la expresión regular que denota (@). 3 . - a, si a E C es la expresión regular que denota ( a ) . 4 . - Si r y S son expresiones regulares entonces tambien lo son :

i) .- r.s que denota al lenguaje L(r).L(s) ii) .- r + S que denota al lenguaje L(r) + L(s) iii).- r* que denota al lenguaje L(r)* iv) .- (r) que denota al lenguaje L(r)

Ejemplos:

Sean C = ( 0,l }

o* = (@,0,00,000, ....) (0+1)* = ( @,0,1,00,11,10,000,001,010 ,.....) 1(0+1)* = ( l,lO,11,100,lOl,lll,.. ...) 10*1 = ( 11,101,1001,10001, .....)

Identidades de la cadena vacia ( @ ) , y del conjunto vacio 9

l . - @ + R = R

2.- @R = R@ = @

3 . - R@ = @R = R

4 . - @* = @

5.- @* = @

Definici6n.- Los lenguajes que pueden ser denotados con EXPRESIONES REGULARES se denominan lenguajes regulares o conjuntos regulares.

Maneio de expresiones reaulares I-

Un conjunto regular puede ser descrito por más de una expresión regular.

Ejemplos :

a).- El conjunto de O's y 1's alternados.

solución : l(O1) * o bien por (10) *1 b).- Las cadenas de O ' s y 1's cuyo segundo símbolo de derecha a izquierda es cero.

solución : (0+1) *O (0+1)

c).- Las cadenas que no tienen la secuencia 01.

solución : 1*0*

PRIORIDAD Nota: Si l o s paréntesis en una expresión regular, no causan confusión, entonces puede omitirse, tomando en cuenta la prioridad del ASTERISCO, PUNTO y MAS.

Siempre que hay dos o más concatenaciones consecutivas, los paréntesis se asocian a la izquierda y lo mismo para el MAS y el ASTERISCO.

Ejemplo :

aba = ((a.b) .a)

a*(aa+bb)*b = ((a*((a.a)+(b.b))*b))

Por lo tanto podemos decir que dos expresiones son equivalentes si denotan al mismo lenguaje.

Desafortunadamente no existen métodos para determinar cuando dos expresiones dadas son equivalentes.

En Liertos casos una expres.ión regular puede ser convertid¿ en otra expresión equivalente utilizando simples identidades.

Algunas de estas identidades son listadas como sigue :

Sean P , Q y R expresiones regulares, entonces

R + R = R

PQ + PR = P(Q + R) PQ + RQ = (P + R ) Q t.

RR* = R*R

(R*)* = R*

@ + RR* = R*

(PQ)*P = P(QP)*

Definición.- Un RECONOCEDOR para un lenguaje L recibe como entrada una cadena X y decide si X pertenece o no al lenguage.

+befinicion. - Un AUTOMATA FINITO DETERMINISTICO (AFD) es una quintupla ( Q , C , G , q , F ) donde :

Q es un conjunto finito de estados.

C es un alfabeto.

6 es una función de transición : Q x C -"+ Q

q , q E Q es el estado inicial.

F , F C Q es el conjunto de estados finales.

Definición.- Un AUTOMATA es un conjunto finito de estados, o una máquina de control finito.

Definición.- Un ESTADO es una configuración particular de un determinado autómata.

Definición.- Una cadena X es aceptada o reconocida por un autómata si comenzando en el estado inicial, después de leer la cadena se llega se llega a un estado final.

Resumiendo 10 anterior podemos decir que,..el lenguaje aceptado por un autómata es el conjunta de cadenas reconc2idas por el mismo.

CICLO DE LO8 AUTOMATA8 1 I.

Exp. reg + AFN t

con @

1 AFD AFN sin @

AUTOMATA FINITO NO DETERMINISTIC0 (AFBI)

En un autómata finito, se tiene la noci6n de determinism0 ya que Para todo g E Q y a E C existe un Único estado q' C Q tal que 9'=t(q,a)

Es decir dados el estado actual y un símbolo de entrada, s610 hay un estado al que podemos transitar.

Un AFN consta escencialmente de lo mismo, scjlo que existe la posibilidad de transitar a varios estados, uno o ninguno.

TRAH8ICION.- Significa estar en un estado actual y por medio de algún simbolo que pertenece a C o por @ llegamos a otro estado.

DESARROLLO I 1.- LECTURA; DE UNA EXPRESION REGULAR

L.

Para la ejecuci6n de este programa se le pide al usuario de como entrada una expresión regular, que debe cumplir las siguientes reglas sintácticas :

1.- Una expresión regular puede empezar con ( , símbolo del alfabeto o @ únicamente.

2.- Después de un ( no debe ir * ni ) .

3 . - Despuds de un * no debe ir *. 4 . - Después de un + no debe ir +, * ni ) . 5.- El último caracter de una expresión regular no debe ser + ni

( 0

6.- El * indica la repetición de cero, uno, o más veces un símbolo o una expresión regular que se encuentra dentro de los parkntesis.

7.- El . indica la concatenación de dos símbolos (o exp. reg.), en este caso se omite la peticion de entrada del PUNTO.

8.- Los paréntesis sirven para delimitar exp. reg. o para indicar precedencia en las operaciones.

9.- Los paréntesis que se ocupen al escribir una expresi6n regular deben cumplir (PAR-IZQ = PAR-DER).

Ejemplos :

(ab* (ab) *a) abba (a*+b*) * ab*c*a a@+b@@* a(b*(c*))a

11.- ASIQNACION DE PRIORIDADES

Durante este paso se le asigna una prioridad a cada operador (MAS, PUNTO, ASTERISCO) y al símbolo del alfabeto, los paréntesis se utilizan para indicar precedencia y orden en las operaciones, el criterio que se tomo para la asignación de prioridades fué :

1.- prioridad del ASTERISCO = 3 (cerradura de Kleen)

2.- prioridad del PUNTO = 2 (concatenacidn)

3 . - prioridad del MAS = 1 ( unión)

4 . - prioridad de un símbolo = a

Ademas la fórmula empleada para asignar prioridad a un elemento es :

prioridad(elem.)=prioridad(operador)+(4x #PAR-IZQ abiertos).

E j emplos :

a(b(c*+d*) * )

a . b . c *

a 2 a 6 a 1 1 9 a 1 1 7

* + d *

111.- CONSTRUCCION DEL AFN con 0

Para construir el AFN de una expresidn regular es necesario localizar el e-emento de menor prioridad, y en caso de ser varios el que se encu,ntre mas a la derecha y dividir en dos subexpresiones a las cuales se les aplicara el mis :a proceso (empezando en la parte izquierda, despues de terminar este análisis continuar con la parte derecha), hasta que la subexpresión más pequeña sea un símbolo del alfabeto aquien despues se le aplicará el operador que le corresponda de acuerdo a las siguientes reglas sintáticas:

1.- Cuando es ASTERISCO todos los estados finales apuntan al estado inicial con @ y el estado inicial tambien se convierte en final.

2.- Cuando es PUNTO los estados finales de la Ira. subexpresión apuntan con @ al estado inicial de da 2da. subexpresión, y ahora el nuevo estado inicial es el de la Ira. subexpresión y los nuevos estados finales son los estados finales de la 2da. subexpresión.

3.- Cuando es MAS se crea un nuevo estado que apunta con @ a cada uno de los estados iniciales de las subexpresiones.

4.- Cuando el elemento analizado es un simbolo del alfabeto se crean 2 estados, el lro. es el estado inicial y el 2do es el estado final, la transición se hace por medio del símbolo (actual) del alfabeto.

Ejemplo :

i=1 m] B i=7 f=5 a 2 a 7 6 a f=8

i=3

f =3

i=3

f=4

Transiciones correspondientes para cada subexpresidn

@

I

@

(b*(c*)) -(3)- (4 ) I

@

a

@

a (b* (c*) ) a

- a @

(3)-(4 I I@ 1 C

Por lo tanto el estado inicial es (1) y el estado final eta (8).

Para la construcción de estos diagrarnas de transiciones se diseño un procedimiento recursivo el cual se explicara mas adelante.

1V.- CONST; 'CCION DEL AFN sin 0

En este paso el objetivo es eliminar las transiciones con @ (de esta manera se reduce el número de estados), el diagrama de transiciones resultante sigue aceptando cualquier cadena del lenguaje que se genera para la expresidn regular correspondiente.

Es muy importante hacer notar que durante este proceso existe una generaci6n de nuevos estados.

El AFD que se genera para el ejemplo anterior lo representaremos como una tabla de transiciones de la sig. manera :

L.

a b c

. o 1 2 3 4 5

1 2 2 edo. inicial (O)

2 2 2 edo. final (3)

3 4 5 2 2 2

3 4 5 3 2 5

V.- AFD (ESTADOS ALCAN2ABLES)

Para encontrar los estados alcanzables en un AFD, recibimos como entrada el AFD obtenido al eliminar las transiciones con @, y descartamos aquellos estados que no son alcanzados (no son necesarios) después de seguir las transiciones de todos los símbolos del alfabeto partiendo del estado inicial.

Para su mejor comprensión representaremos el AFD como una tabla (de edos por elementos del alfabeto).

Ejemplo :

AFD

a b

1 : I 4

AFD (Edos. alcanzables)

a b "

O 1 1 3 1 4

1

3 1 4 1

4

Para el ejemplo anterior a(b*(c*))a

los edos alcanzables del AFD son :

a b c

2 3 4 4 5 5

L.

que corresponde al mismo AFD obtenido en el paso anterior.

I RESUMEN TEORICO

Después de dar una breve explicación con respecto a la teoría

que implica una expresión regular hasta obtener los estados

alcanzables de la misma, en lo que resta de este manual se

explicaran las estructuras de datos, algoritmos y procedimientos

utilizados para la eleboración del este programa, en los casos

donde sea necesario se mostraran ejemplos para su mejor

comprensi6n.

i ESTRUCTURAS DE DATOS Y VARIABLES GLOBALES

h.

9 1 . - Variables Globales

Alf-opc[MAX]

Contiene los elementos que se le permite al proporcionar al usuario para declarar su alfabeto opcional de entrada. El número máximo de caracteres permitibles es de 80.

Edos - Alc [MAX]

Contiene únicamente el caracter ' S ' o In1.

L-Edos [MAX]

Contiene un grupo de estados alcanzables para una expresión regular.

Expr LIMITE]

Es un arreglo de registros donde cada uno de ellos tiene dos campos, uno para el símbolo de la expresidn (termino) y otro para la prioridad de este símbolo (prioridad).

cont-edos

Es un contador de estados que sirve para ir creando los estados de LISTA.

estados

Es un contador de estados que sirve para ir creando los estados de L-SIMB.

bandera

condición que nos sirve para saber si un estado ya fue creado o no.

nu-elem Es el número de dlementos diferentes de un alfabeto (Si se

repite un símbolo en la expresión regular únicamente cuenta una vez). Los operadores ASTERISCO, PUNTO, MAS, PAR-IZQ y PAR-DER no pertenecen al alfabeto.

b) .- T . D . A ,

struct nodo

Contiene los campos : I-

símbolo.- Puede ser un símbolo del alfabeto o @. Dum edo.- Es un número de estado.

u.- Es un apuntador a otro struct nodo.

struct tabla

Contiene los campos :

- edo.- Es un número de estado.

sis nodo.- Es un apuntador a un struct nodo.

sis tabla.- Es un apuntador a un struct tabla.

struct sdo-fin

Contiene los campos :

&Q.- Es un estado final. u.- Es un apuntador a un struct edo-fin.

struct lista - simbolos Contiene los campos :

sia simb.- Es un apuntador a un struct.

símbolor301.- Es un arreglo que puede contener a lo m8s 30 símbolos.

distinsuib1e.- Este campo solo puede contener un caracter I s t o In1.

num edo.- Contiene un número de estado.

ais edoc - Es un apuntador a una lista de edos, es decir, a un struct edo-fin.

L - SIMBOLOS, L-SIMB son variables globales del tipo struct lista símbolos. -

ED0 - FIN es variable global del tipo struct edo-fin.

LISTA y L-EDOS - ALC son variables globales del "ipo struct tabla.

A continuación se describen los procedimientos que se utilizarón para la realización del programa.

t.

PROCEDIMIENTOS Y ALGORITMOS PARA OBTENER UN AFD 1

Realiza la lectura de la expresidn regular, en caso de ser una expresión no correcta, manda un mensaje de error en otro caso procede de la siguiente forma (secuencialmente).

- Lee el alfabeto de entrada. - Lee la expresión regular. - Se verifica que esta sea sintacticamente valida. - Se aplica el método de asignación de prioridades. - Se crea el AFN con @

- Se crea el AFN sin @

- Y finalmente se obtiene el AFD (Estados Alcanzables), que se representa por medio de una matriz de estados (renglones) por

símbolos del alfabeto (columnas).

entrada:

edo-ini=O / * edo inicial utilizado en el AFN con @. */ CEF=NULL / * lista de edos finales para el AFN con @. */ LISTA=NULL / * estructura que simula el AFN CON @. */ ‘ont - edos=O / * contador de edos utilizado en el AFN CON @. */ L-SIMB=NULL / * estructura que representa el AFN sin @ */ estados=O / * contador de edos utilizado en el en la creación

del AFD */ L - EDOS - ALC=NULL / * estructura utilizada para la creación de

edos alcanzables finales. */

TEMPO=NULL /* lista que contiene los edos finales definitivos de la expresidn regular. */

salida:

edo inicial, edo(s) final(es) y los edos alcanzables del AFD representados en una matriz como se menciond anteriormente.

módulos subordinados:

Leer alf-opc; quita blancos; ALFABETO ; ValidaExp; Lee-alfabeto; Asigna-prioridad; Automata: minimiza-transiciones; EliminaLista; Lee edos-diferentes; L-Edos-Pre-alcanzables; Enlista-edo; Asigna-Edos-F; imprime-transiciones; imp-edos-alcanzables;

Lee los elementos que el usuario opcionalmente desee integrar al alfabeto y descarta al ASTERISO, PUNTO, MAS, PAR-IZQ y PAR-DER.

entrada:

Arreglo de char (vacio).

salida:

Alfabeto opcional.


ninguno

Eliminima los espacios en blanco al inicio de la cadena.

entrada:

cadena de caracteres.

salida:

cadena de'caracteres sin espacios en blanco al inicio de esta.


ninguno.

ALFABETO ( 1

Verifica que todos los elementos leidos pertenezcan al alfabeto correcto.

entrada:

alfabeto, expresión regular.

salida:

El número de símbolos de la exp. reg. (cuando todos pertenecen al alfabeto) y un cero en caso que al menos un símbolo no pertenezca al mismo.

m6Uulos subordinados:

pertenece-al-alf; char valido: -

pertenece-alalfo

verifica si un caracter de la expresión pertenece o no al Alfabeto Opcional.

entrada:

Alfabeto Opci"na1.

salida:

verdadero (1) o falso ( O ) .

m6dulos subordinados:

ninguno

Charvalido (1..

comprueba que un caracter sea operador, parentesis o @. entrada:

un caracter.

salida:

verdadero o falso.


ninguno.

Verifica que la expresión regular sea valida para el alfabeto correspondiente, cumpliendo las reglas gramaticales para una exp. reg. mencionadas anteriormente.

entrada:

alfabeto, exp. reg.

salida:

verdadero o falso.

mddulos subordinados:

ninguno.

entrada:

la posición de un caracter de la expresión regular.

salida:

verdadero o falso.

módulos suborbinados:

ninguno.

a a l f a b e t o l l

4.

En este procedimiento se encuentra el número de elementos no repetidos que pertenecen al alfabeto. Por ejemplo para la expresidn reegular ab*(ab)*a*b, son dos los elementos (a,b) que se asignan al alfabeto.

entrada:

alfabeto, cadena de caracteres.

salida:

número de elementos diferentes.


Encuentra-elem;

Encuentra-elem(L

verifica si un elemento se encuentra en el alfabeto final.

entrada:

alfabeto temporal, un caracter y su posición en el arreglo.

salida:

verdadero o falso.


ninguno.

Asigna prioridades para los símbolos de la expresi6n regular, incluyendo la prioridad del PUNTO donde sea necesario. el TDA es :

t. - termino - - prioridad EXP ""

ejem :

a (b (c*+d*) * )

a . b . c *

a 2 a 6 a 1 1 9 a 1 1 7

* + d *

Exp[i] O 1 2 3 4 5 6 7 8 9

Los casos en los cuales se va a crear un PUNTO para para el campo termino y su prioridad correspondiente para el campo prioridad son los siguientes.

1.- Cuando un símbolo que pertenezca al alfabeto va seguido por otro símbolo que pertenece al mismo o por un PAR-IZQ.

2.- Cuando un ASTERISCO va seguido por un símbolo del alfabeto o por un PAR-IZQ.

3 . - Cuando un PAR DER va seguido por un símbolo del alfabeto.

entrada:

-

expresidn regular.

salida:

el límite derecho del arreglo.


PRIORIDAD;

Los únicos elementos de una exp. reg. a los que podemos obtener su prioridad son : símbolo del alfabeto, ASTERISCO, PUNTO y MAS.

entrada: t.

un caracter.

salida:

la prioridad de ese caracter.


ninguno.

Crea una lista de estados, con sus respectivas transiciones (incluyendo con @ ) , es decir, crea un AFN con @. Primero se localiza la posicidn en Exp donde se encuentra el

operador de menor prioridad, en caso de existir dos o más posiciones con la misma prioridad, se toma aquella que se encuentra mas a la derecha. Entonces el arreglo se divide en dos partes y se realiza el mismo procedimiento, ejecutandose primero la parte izquierda y después de ejecutarse completamente y regresando las transiciones correctas(operaciones con ASTERISCO, PUNTO o MAS), continua el mismo proceso con la parte derecha y al regresar la última llamada recursiva de Automata se ha creado una lista de nodos que contiene las transiciones para cada edo.

Los criterios para crear estados con sus respectivas transiciones son los ya mencionados anteriormente para el ASTERISCO, PUNTO y MAS.

La lista de edos que se crea para a(b(c*+d*)*) es :

1

1

i

1

Algoritmo:

Automata (Lim izq, Lim der) empieza

- - edo ini1,edo ini2,edo_ini3,sig : c.entero CEFi,CEF2,CEF3 : struct Edo-fin Si (Lint-izq=Lim-der) empieza

edo ini=caso base(Lim-izq); CEFZenlistapdo (cont-edos) ;

termina

empieza otro

sig=ind-men (Lim-izq, Lim der) : Si (Exp[sigJ.temino==A~TERICO) empiesa Automata(Lim-izq,sig-1); Ha~-transiciones(edo_ini3,CEF3); Haz-nula(CEF3) ; edo_ini=edo_ini3; CEF=enlista_edo(edo_ini3); termina

empieza otro

Automata (Lim-izq, sig-1) ; Automata (sig+l, Lim-der) : Si (Exp[sig].termino==MAs) empieza

edo-ini=Es-un-or(edo ini1,edo ini2); CEF=une_edos_fin(CEFi,CEF2);

- termina

otro empieza

Haz-transiciones(edo_ini2,CEF1); edo ini=edo-inil; Haz-nula (CEF1) ; CEFzCEF2 ; termina

termina termina

termina.

entrada:

Límite izquierdo, Límite derecho.

salida:

estado inicial, edo ( s) final (es) , LISTA.


caso-base; enlista-edo; ind-men; Haz-transiciones; Haz-nula; Es-un-or ; une -edos - fin:

t.

caso base().

Se crea el estado inicial y final para un símbolo del alfabeto, cada vez que se entra a este procedimiento se incrementa el contador de estados.

Además se agrega el nuevo-edo con su transición a LISTA.

Ejemplo:

nuevo-edo -"+

1

entrada:

Límite izquierdo.

salida:

un nuevo estado con su respectiva transición.


enlista:

pnlista (1

Agrega el nuevo estado a LISTA.

entrada:

LISTA, nuevo estado

salida:

LISTA.


ninguno.

enlista edo 0 L.

Agrega un estado final a la lista de edos finales (Em-FIN)

entrada:

contador de edos.

salida:

un nodo que contiene un edo final.


ninguno.

Localiza la posición del índice del arreglo, donde se encuentra el operador de menor prioridad. La lista se recorre de izquierda a derecha.

entrada:

Lim. inferior y superior del arreglo.

salida:

posición del índice menor.


ninguno.

En este procedimiento se realizan las transiciones correspondientes al operador ASTERISCO.

Se localiza la posición de cada estado final en la LISTA y se hace una transición con @ al estado inicial.

entrada:

edo inicial, lista de edos finales.

salida: l.

LISTA.


Localiza; '

transición; 8

Localiza (1

Se busca la posición en la LISTA del estado que queremos buscar.

entrada:

LISTA, edo . salidat

un apuntador a edo en la LISTA.


ninguno.

transioion ( 1

Se realiza una transición para un símbolo del alfabeto en un nodo del tipo Elemento.

es decir

entrada:

un símbolo del.~"alfabeto, un edo.

salidat

un nodo del tipo Elemento.


ninguno.

Haz nula (1

Libera espacio de memoria.

entrada: L.

Lista de edos finales.

salida:

lista vacia (nula).


ninguno.

Es un o r 0

En este procedimiento se realiza las transiciones correspondientes al operador MAS.

Se emplea un nuevo estado inicial y se hacen las transiciones con @ a los anteriores estados iniciales. Se agregan las transiciones creadas a LISTA.

entrada:

edo inicial1 y edo inicial2 (de cada subexpresión).

salida:

un nuevo edo inicial.


crea-nodo-lista; transición: enlista:

crea nodo lista0

Regresa una estructu. \ del tipo tabla.

tabla -"+ sig-nodo

sig-tabla

une edos fin0

Concatena dos listas de estados finales (del tipo Edo-fin).

entrada: L.

dos listas de edos finales.

salida:

una lista final.


ninguno.

crea nodo elem( 1

Regresa una estructura del tipo Elemento.

num edo

nodo -"+ I f i t sig

simbolo

minimiza transiciones0

Este procedimiento inicia realizando las transiciones con @, apartir del edo inicial, entonces crea una lista de edos que son alcanzados con transiciones de @, incluyendo al edo inicial.

Para esto se auxilia de una lista de TDA L-SIMB. Después de encontrar la lista de edos obtenidos con transiciones de @. Se hacen todas las combinaciones, con cada símbolo del alfabeto para cada uno de los estados que pertenecen a esta lista, utilizando el procedimiento recursivo Busca edos y así obtenemos cada uno de los nodos que pertenecen a L SIMB, Después de encontrar la infonnaci6n correspondiente a un nodo de este tipo, se verifica si la lista de estados actual, se parece a alguna anterior, en caso que as1 sea se coloca una In1 en el campo distinguible y en el campo num-edo el mismo número de estado que corrE xmde a la lista que se parece, de otra manera se coloca una ' S I en el campo distinguible y el númer, que corresponde al incremento de estados se coloca en el campo num-edo.

La lista que se crea para a(b(c*+d*)*) es:

t.

Algoritmo:

minimiza-transiciones(num-elem,edo_ini) empieza

auxiliar2,temp : Edo-fin apaux,nuevo_nodo,apaux2 : Lista-simbolos cad[30],simbolo : char i,pos :entero inicializa-Lista-simb(edo-ini); apaux=posiciona(L-SIMB); mientras (apaux <> NULL)

empieza si (apaux->distinguible='s') empieza

i-O ; mientras (icnum-elem)

empieza simbolo=Alfabeto[i]; nuevo-nodo=crea_nodo-L-simbolos(); nuevo nodo->sig-simb=NULL; strcpy(cad, apaux->simbolo) ; pos=aparece-simb(Alfabeto,simbolo); strncat(cad,Alfabeto+posrl); strcpy(nuev0-nodo->simbolo,cad); nuevo nodo->lis-edos-NULL; temp=Euevo-nodo->lis-edos; auxi l iar2=apaux-~l is_edos; mientras (auxiliar2 <> NULL)

empieza Busca~edos(&temp,auxiliar2->edo,simbolo)~ auxiliar2=auxiliar2->sig;

termina apaux2=posiciona(L-SIMB); bandera=O; mientras (apaux2 <> NULL AND NOT bandera)

empieza si (Listas~iguales(apaux2-~lis~edos,temp))

otro

termina si (bandera=l)

empieza

bandera=l;

apaux2=apaux2->sig - si*;

nuevo-nodo->distj mible='nt; nuevo nodo->num~edo=apaux2->num~edo;

termina

empieza

- otro

nuevo nodo->distinguible='s'; nuevoznodo->num-edo=estados; estados=estados+l;

termina nuevo - nodo->lis-edos=temp;

Enlista-nodos(&L-SIMB,nuevo-nodo); i=i+l;

termina termina

apaux=apaux-xig-simb; termina

termina. t-

entrada:

número de elementos,edo inicial.

salida:

una lista del tipo lista-simbolos (L-SIMB).


inicializa - Lista-simb; posiciona; crea nodo-L-simbolos; aparzce-simb; Busca-edos; Lista iguales; Enlista-nodos;

inicializa Lista simb0

Inicializa las transiciones con @ de LISTA apartir del edo-inicial, crea un nodo (del tipo Lista-simbolos) y almacena los valores iniciales.

nodo ---+Vt* lista de edos

Hace una llamada al procedimiento recursivo Busca-edosl y obtiene una lista de edos que son alcanzados apartir del edo inicial con @. entrada:

edo inicial.

salida:

nodo del tipo Lista-simbolos.

módulo8 subordinados:

crea-nodo-L-simbolos; Enlista; Busca-edosl; Enlista-nodos; I.

crea nodo L aimbolosC1

regresa una. estructura del tipo Lista-simbolos.

distinguible num-edo

"+ + 1 is-edos I

simbolo sig - simb

En este procedimiento se verifica si un estado se encuentra en la lista temp, si asi es, no se modifica temD, en caso contrario se busca la posición que le corresponde a este número de edo para que la lista quede ordenada en forma creciente.

entrada:

una lista de edos, un edo.

salida:

una lista de edos.


ninguno.

Busca-edos (1

La tarea de este procedimiento recursivo, es realizar las transiciones de un estado ir. luyendo las que se hacen con @ despu6.s de alcanzar la correspondiente al simbolo actual del alfabetc y así los estados que son alcanzados se almacenan en una lista. Si no se puede realizar ninguna transición con el simbolo se regresa una lista vacia.

Las transiciones se realizan utilizando LISTA.

Algoritmo:

Busca-edos(&temp,edo,simb-alfabeto) empima band : entero aux : Lista I-

aux2 : Elemento aux=Locqliza(&LISTA,edo); aux2=aux->sig-nodo; band==O : mientras (aux2 <> NULL AND band=O)

empieea si (aux2->simbolo=simb~alfabeto) empieza

si (NOT Localiza~edo(temp,aux2->num_edo)) .empieza

Enlista(&temp,aux2->num_edo); Busca edosl(&temp,aux2->num_edo,"); band=i; termina

termina aux2=aux2->sig;

termina termina.

entrada:

Lista de edos,edo,símbolo del alfabeto.

salida:

Lista de edos (temp) . m6dulos subordinados:

Localiza: Localiza-edo; Enlista; Busca-edosl;

Busca ets l (1

Partiendo de un estado, alamcena en una lista todos aquellos que son alcanzados con transiciones de @ únicamente.

La primera pasada la reallza partiendo del estado inicial de LISTA, verifica todas las transiciones consecutivas de @ y los estados por los que va pasando (incluyendo el estado inicial), los almacena en una lista temporal.

Algoritmo:

Busca-edosl(&temp,edo,simb_alfabeto) empieza

aux : Lista aux2 : Elemento I.

aux=Localiza(fLISTA,edo); aux2=aux->sig-nodo; mientras (aux2 <> NULL)

empieza si (auxi->simbolo=simb-alfabeto) empieza

si (NOT Localiza~edo(temp,aux2->num~edo)) empietxa Enlista(&temp,aux2-~nuxn~edo); Busca~edosl(tternp,aux2-~num~ed0,~@~) termina


termina termina.

entrada:

Lista de edos,edo,símbolo del alfabeto.

salida:

Lista de edos (temp).

módulo8 8ubordinado8:

Localiza; Locsliza-edo; Enlista; Busca-edosl;

Verifica que un estado se encuentre en una lista.

entrada:

Lista de edos,edo.

salida:

verdadero o f a l s o .


ninguno.

Enlista nodos()- L.

Agrega un nodo del tipo Lista-simbolos (el cual ya tiene toda su información) a la lista L-SIMB.

entrada:

L-SIMB,nodo.

salida:

L-SIMB . m6dulos subordinados:

ninguno.

posiciona()-

Coloca un apuntador al inicio de L-SIMB.

entrada:

lista del tipo L-SIMB.

salida:

un apuntador a L-SIMB.

m6duloa subordinados:

ninguno.

aDarece-simb ( 1

Regresa la posición donde se encuentra el símbolo actual del alfabeto.

entrada:

Alfabeto,símbolo.

salida;

posicion de un símbolo del alfabeto.


inguno .

Primero se compara si las dos listas tienen igual número de elementos, de ser asi compara elemento a elemento.

entrada: t.

dos listas de edos (ordenadas en forma creciente).

salida:

verdadero o falso.


elementos;

elenentosti

Cuenta el número de elementos de una lista de estados.

entrada:

Lista de edos.

salida:

número de elementos de la lista.


ninguno.

Elimina una lista con cada uno de sus nodos (libera espacio de memoria).

entrada:

Lista de elementos.

salida:

Lista vacia.


ninguno.

Se almacenan los valores correspondientes para Edos Alc[MAX] y L-Edos[MAX] de la siguiente manera.

-

Edos-Alc[J almacena una Is8 o In1+ dependiendo si el, arreglo L-edos en la misma posicibn que Edosplc, contiene un estado distinguible.

L-Edos[] contiene un grupo de estados alcanzables para una expresión regular.

Edos-Alc y L-Edos deben tener la misma longitud.

Ejemplo:

L-Edos

s n s s n s Edos-Alc

o 1 2 3 4 5

o 1 2 3 4 5

entrada:

lista de edos finales que corresponde a LISTA, L-SIMB.

salida:

el número de edos distinguibles, L-Edos, Edos-Alc.


Localiza-edo;

En este procedimiento se crean las transiciones de los edos alcanzables (totales), con cada uno de los simbolos del alfabeto, conforme se va creando un nodo (que contiene un edo alcanzable) con todas sus transiciones con los simbolos del alfabeto de entrada, se va agregando cada nodo a la lista L-EDOS-ALC.

La lista resultante para a(b(c*+d*)*) es :

L-EDOS-ALC I

Algoritmo:

L-Edos-Pre-alcanzables(edos,simb,Listar) empieza

i, j : entero auxl : Elemento aux,nodo : Lista apl : Lista-simbolos apl=Lista->sig simb; i=o : mientras (i<edos) / * # de edos alcanzables */

-

empieza nodo=crea-nc 3-Lista ( ) ; nodo->edo=L-dos[i]; nodo->sig nodo=NULL; nodo->sig-tabla=NULL; - j=o; mientras (j<simb) / * num. de simbolos del alfabeto */

empieza si (nodo->sig-nodo=NULL)

empieza nodo->sig~nodo=transicion(Alfabeto[jl,apl-~n~~~~~~~ j=j+l; apl=apl->sig-simb;

termina

empieea l.

otro

aux-nodo ; auxl=aux->sig-nodo; mientras (auxl->sigoNULL)

auxl->sig=transicion(Alfabeto[j],apl->n~~~~~~~~ j=j+l: apl=apl->sig-simb;

auxl=auxl->sig;

termina termina

ENLISTA-PRE-ALCANZABLES(&L-EDOS-ALC,nodo); i=i+l;

termina termina.

entrada:

num. de edos alcanzables,número de elementos del alfabeto,L-SIMB.

salida:

L-EDOS-ALC.

m6duloa 8ubOrdinadO8:

crea nodo-Lista; transition; ENLISTA-PRE-ALCANZABLES;

Agrega un nodo que contiene un edo alcanzable y sus transiciones con cada símbolo del alfabeto, a la lista L-EDOS-ALC, que sera nuestra lista final de edos alcanzables.

entrada:

L-EDOS-ALC,nodo.

salida:

L-EDOS-ALC.


ninguno.

Almacena en TEMPO una lista de edos alcanzables se ordenan en forma creciente.

entrada:

TEMP0,edo.

salida:

TEMPO.


ninguno.

Se agrega a TEMPO, el estado que pertenece a una transición con un símbolo del alfabeto, sino se encuentra se agrega a TEMPO y se ordena en forma creciente, de otra manera no pasa nada.

Algoritmo:

Asigna-Edos - F(&TEMPO,edo) empieza aux : Lista aux2 : Elemento aux=Localiza-Edos-Alc(&L-EDOS-ALC,edo); aux2=aux->sig-nodo; mientras (aux2oNULL)

empieza si (NOT Localiza~edo(TEMPO,aux2-~num~edo))

Enlista edo(TEMPO,aux2->num-edo); Asigna-~dos-F(&TEMPO,aux2->num_edo);

empieza


termina termina.

entrada:

TEMP0,edo.

TEMPO.


Localiza-Edos-Alc; Localiza-edo; Enlista-edo; Asigna-Edos-F;

m o s - A l a ( 1

Localiza un edo en L-EDOS-ALC.

entrada:

L-EDOS-ALC,edo.

salida:

un apuntador al edo en L-EDOS-ALC.


ninguno.

Imprime una tabla de edos alcanzable8 con sus respectivas transiciones esta tabla es la última que finalmente obtenemos.

Para la exp. reg. a(b(c*+d*)*) obtenemos :

a b c d

O 1 2 2 2 1

2 2 2 2 2 2 3 2 2

2 2 4 5 5 2 2 4 5 4 2 2 4 5 3

~ ~~~~

entrada:

L EDOS ALC. - - 1146513 salida:

tabla impresa.


ninguno.

imp edos a l c a n z a b u R.

Imprime los edos alcanzables que son finales, es decir, aquellos L-edos[i] cuando Edos-Alc(i]=lsl.

Para la exp. reg. a (b (c*+d*) *)

ESTADOS FINALES : ( 3 ) , (4 ) y ( 5 )

entrada:

Lista de edos finales.

salida:

impresión de estados finales.


ninguno.

I. Requerimiento del programa.

11. Instalación del programa. t.

111. Ejecución del programa.

a).- Elección de algún alfabeto no opcional.

b).- Elección del alfabeto opcional.

c).- Elección erronea.

d) . - Salida. IV. Generación de resultados.

a) .- Por pantalla. b) . - Por impresión.

V. Ejemplos.

REQUERIMIENTO DEL PROGRAMA

L.

Para utilizar el programa se necesita de lo siguiente :

1.- Una computadora Personal con una o dos unidades de disco

flexible, o un disco duro.

2.- Almenos 256 kilobytes de memoria RAM. 3.- Sistema Operativo DOS 2.0 en adelante.

4.- Monitor monocromático o de color.

I INSTALACION I 8-

1.- Inserte el disco del sistema (en caso de no trabajar con disco duro), en la unidad de disco.

2.- Cuando aparece el prompt, introduzca ExpReg (mayúsculas y/o minúsculas) y presione return.

a: > expreg -1

En seguida apareceran dos pantallas de presentacidn y despuks otra mds que contiene un menú de alfabetos (est8 pantalla ser8 la principal).

A L F A B E T O S

Ceros Dígitos Letras Alfanumérico Opcional -

Para salir presione ESC

EJECUCION DEL PROGRAMA

L.

Acontinuación se muestran todas las posibles alternativas que podemos elegir en el menú principal.

a).- Elección de alaún alfabeto no oxionak

Al momento de aparecer el menú principal, las opciones que debemos escoger son C (ceros y unos), D (digitos), L (letras) y A (alfanum&rico), que son las letras que se encuentran brillando y parpadeando en la pantalla.

Al elegir un alfabeto se obtendrá una tabla correspondiente al autómata finito con transiciones de Q y finalmente otra que corresponda al autómata finito deterministico. Cuando la exp. reg. no sea correcta aparecerá un mensaje en pantalla, en otro caso se le pedirá al usuario que continue con otra exp. reg. que debe permanecer al mismo alfabeto que selecciond o tiene la opcidn de regresar al menú principal y elegir otro alfabeto que estará sujeto al mismo proceso mencionado anteriormente.

En seguida se muestran todas las posibles alternativas que podemos elegir en el menú principal.

Para esto debemos oprimir la tecla correspondiente al alfabeto que deseamos sea el de entrada, supongamos que elegimos la letra L, posteriormente se limpia la pantalla anterior y aparece la siguiente:

Escribe tu expresión regular b

l.

I

En la cual debemos escribir la expresi6n regular (con letras unicamente), la cadena que escribimos, no debe exceder una longitud de 80 caracteres. En caso que nos equivoquemos al escribir la expresión regular, el cursor se encuentra en una posición después del último caracter de la cadena y podemos borrar hacia la izquierda con la tecla baokspace o su equivalente en el teclado español. Y así, volver a escribir la expresión regular que consideremos correcta, posteriormente oprimimos la tecla return para confirmar la aceptación de la cadena de entrada.

Cuando la exp. reg. es sint6cticamente correcta desaparece la pantalla actual, y al’arece la siguiente que representa el AF con transiciones de Q en la siguiente forma:

ED0 INICIAL : 5 ED0 (S) FINAL(ES) : 2 3

I 1

Oprima cualquier tecla para continuar

La cual representa las transiciones de cada estado, con cada uno de los símbolos del alfafeto, así como con @.

Posteriormente se visualiza la tabla de edos que corresponde al aut6mata finito determinístico.

AUTOMATA FINITO DETERMINISTIC0

a b c o 2 1 2 1 1 3 2 2 3 3 2 3 1 2 3

ED0 INICIAL O ED0 (S) FINAL( ES) : 1 2

Oprima cualquier tecla para continuar o ESC salir

Los estados aparecen en la primera columna, el primer rengl6n muestra los elementos del alfabeto, de tal manera que al combinar los estados de la primera columna con cada uno de los simbolos del primer renglón se obtienen las transiciones de cada estado con cada uno de los símbolos y escribiendo el estado que se obtiene haciendo coincidir la columna (edo) ,.por renglón (simba10 del alfabeto).

Posteriormente aparece el edo inicial (siempre ser& cero) y el (los) estado(s) final (es) . Cuando las transiciones del autómata requieren listar muchos

estados, se desplegaran en la pantalla como pdginas, simplemente orpimiendo cualquier tecla, hasta que finalmente se muestren los estados finales, y después aparece un mensaje, para continuar dentro dentro del programa y regresar al menú principal.

Es importante recalcar que los símbolos válidos del alfabeto LtBtraa, son considerados diferentes entre mayúsculas y minúsculas aunque se trate del mismo caracter.

e j emplos :

a es diferente de A b es diferente de B

En el caso que una expresión regular sea escrita sintácticamente mal, aparece la siguiente pantalla:

La expresión regular

a+b(a*(b*)a*b

Oprima cualquier tecla para continuar o ESC salir

en la cual se escribe la exp. reg. que fud dada como peticibn de entrada, pero no nos dice donde está mal escrita sint8cticamente.

De igual forma para volver a escribir otra exp. reg. podemos oprimir cualqu.ier tecla.

La manera de regresar al menú de ibs alfabetos, es despuds de terminar la visualización del AFD.

b1.- Elección del alfabeto omional.

Al estar visualizando el menú principal oprimimos la tecla que corresponde a la letra O y en seguida aparece la siguiente pantalla :

Escribe los elementos de tu alfabeto

I I

y empezamos a escribir l o s caracteres que deseemos formen alfabeto de entrada.

el

Si un caracter lo repetimos varias veces, unicamente estará el símbolo de este tipo en el alfabeto.

En el caso que se elija como elemento al ASTERISCO, MAS, PUNTO, PAR-IZQ o PAR-DER, no se agregaran al alfabeto de entrada, porque su función de ellos dentro del programa no es servir como un caracter valido de UT . exp. reg. más bien, como un operador.

Las letras mayúsculas y minúsculas tambien se consideran slmbolos diferentes.

Al terminar de escribir los caracteres candidatos a simbolos del alfabeto confirmamos, oprimiendo la tecla return, desaparece esta pantalla y aparece aquella que nos pide que demos como entrada la expresidn regular (descrita anteriormente) y analogamente al caso anterior si la expresión es escrita correctamente aparece la pantalla final, que muestra el AFD ,.y en caso contrario la pantalla de mensaje de error, y después oprimimos cualquier tecla para regresar al menú principal.

c).- Elección erronea.

Al tener la pantalla inicial si oprimimos una tecla diferente al caracter C , D, L, A, O o la tecla ESC, regresamos otra vez al menu principal, unicamente aparece un mensaje para continuar.

A L F A B E T O S

Ceros Dígitos Letras Alfanumérico Opcional

Oprima cualquier tecla para continuar

Hasta que obtengamos una opción correcta.

dl .- Salida. En el menú principal se muestra la opción de salida, oprimiendo

la tecla ESC, y regresando al sistema.

L GENERACION DE RESULTADOS &.

a) .- Por Dantalla. unicamente! hay que correr el programa ejecutable y estar

introduciendo’expresiones regulares para el alfabeto seleccionado, l o s resultados se visualizaran en pantalla.

b) .- Por imtxesión. debemos conectar nuestra impresora a la computadora personal,

insertar nuestro disco flexible que contiene el programa ejecutable en la unidad de disco, hay que estar seguros que la impresora está en linea, ahora oprimimos c t r l P para activar la impresora, a continuación damos el siguiente mandato :

a>expreg J

y empezamos a correr nuestro programa por pantalla como lo describimos anteriormente y asi los resultados serh impresos.

cuando terminemos de ejecutar nuestro programa volvemos a dar el mandato ctrl. P para desactivar la impresora.

En conclusidn el usuario tiene la alternativa de escoger cualquiera de l o s procesos mencionados anteriormente según sus conveniencias.

I EJEMPLOS

L.

Acontinua'ción se muestran algunos ejemplos en 10s cuales para esa expresi'dn regular se obtiene una tabla que contiene SU AFD, edo inicial y edo(s) final (es) . a) . - (a*+b*) *

a b

2

edo inicial O edos finales : O 1 2

c) .- a@+b@@*

q-ij a b

2 3 edo inicial O edos finales : O 1 2

b) * - a(b(c*+d*)*)

a b c d

1 2 2 2 2 3 2 2 2 2 2 2 2 2 4 5 2 2 4 5 2 2 4 5

edo inicial O edos finales : 3 4 5

d) .- abc*+8+9* a b c 8 9

1 2 2 3 4 2 5 2 2 2 2 2 2 2 2 2 2 2 2 2

' 2 2 2 2 4 ' 2 2 6 2 2 2 2 6 2 2

edo inicial O edos finales : O 3 4 5 6

e) . - (O+l@@) *@ o 1

f) .- 7 8 * ( ( 7 8 ) * )

7 8

O

2 1 2 1 1 2

1 2

edo inicial , O edos finales : O 1 2

o

3 2 5 3 4 4 2 5 3 2 2 2 3 4 1

1.1 2

edo inicial O edos finales : 1 4 5

~ ~~

CONCLUSIONES

Finalmente puedo decir que todos Los objetivos planeados fueron

obtenidos favorablemente, para el buen funcionamiento del paquete,

con la alte:rr\ativa que aún se puede modificar para obtener el

último paso, que consiste en llegar a alcanzar un Autómata Finito

Deterministic0 óptimo, es decir, un AFD con el número mínimo de

estados con sus respectivas transiciones.

:include (stdi0.h)

:include (a1lcc.h) :include (std1ib.h) tinclude (cmio.h) tinclude (ctype.h) tinclude {string.h) :include "define.c' nain( 1 I portada0;

- inicia( 1; mu-cI1Fmas ( 1 ;

)

It """""""""""""""""""""

-,

+

""""""""" "." t/

I.

? 1tt;

bita los blancm al inicio de l a cadma

quita-biancoskhar cad[:l,char texpr)

t i=O; xpr-'\O'; ile(cad[il -= ' ' ) itt;

ile(cad[il != '\O' &d cad[il I = ' '1 *

texpr-cad[il; exprtt; itt;

texpr = ' \ O ' ;

Regresa el n ( l m de elementos repetid(% que pertenecen a l alfabeto *I

lee-alfabetdchar #,char Wladena,int fnw-elm)

it k, i , j ; Mr Tecp[MXl; : O ; j=O; rile (cadena[il !E ' \ O ' ) I

if (cadena[ il ! =IIsTERI!Xil &A cadenai i 1 !=¡'N 11 cadena[ i 1 ! =PMENl-IZQ 111 cadena[ i 1 ! :PWEWT-DER 4 1 cadena[ i 1 ! = P M O &11 cadena[ i 1 !I '@'

Terp[jl=cad~na[il; jtt;

1 i t t ;

1 erp[ jl:'\O'; =O; $=o; ~[ i l :Teq[kl ; tt;ktt;

rhile(k !: jJ

if ( !Encuentra_elea(CI,Terp[al,i) 1 I A[il=Tenp[kl;

1 kt+;

1

itt;

M11:'\0'; wur-eleazi;

t " "_""""""" """_ *I

1.

It """"_"" "-l_"- """" *l L.

1s """""""""""""""""""" t/

It Se d e w e l w un CERO cuando el Alfabeto es elegido equivocadamente y el numero de sirbplos de la expresion en caso contrario *I

default : return(siaboio=OI;

""""""~""""""""~ 1.1

c verifica si un caracter de la expresirh pertenece o no a l a exp. reg. */

perten~e-al_alfab(cha~r caracterl

"""_""""""""""""".""""""" tl

int char-validokhar caracter)

lnt ValIdaExpkhar aliab,char Kadena)

L.

int PRIOATDI\D(char caracter)

"""""__""-"___""""- f/

En este procedimiento se asignan las prioridades para los sirbolos de l a pxpmib, regular. f/

kignagrior idadkk tcadena,int flir-des)

I.

"""_ """" "l"__l_l- """" +i

ita funcion regresa el indice del Arreglo, en donde se encuentra el aperadar de far priaridad, la lista se recorre de irquierda a ~ETK~M. */

t i,sin-ind,ain; n-ind-ini:; nfxptain_indl.prioridad; Ir (i:inftl;i(-sop;it+)

if(ExpCi1,prioridad (= rill1

rin=Exp[il.prioridad; ain-indri;

{

1 lturn(rm-indl;

- "" __""" """"" "-.-""""""" "__." f l

t i tuncibn recursiva rqresa el estado inicial y el (los) estadds) final(& rbih crea una lista de estados c m y15 respectivas transiciones cm '@' decir crea las tran~icimes de un AFN IIUI trwsicians de c! rí

"""""" "" """""" *I

crea el estado inicial y final para un sipbolo f/

L.

Elerento Yransicion(char si8,int &-des)

"""_"""" - """-1""" """" * I

€I este procediaimto se realizdn las transiciones correspandientes al operador ffilERIsW */

Regresa l a posicibn en la LISTA, del e:ienento que querem buscar *I

Lista *localiza(LISIA,edo) sta **LISTA; t d a ;

'3" _""""""""""""""""""" f/

I* Hace nula una lista dP edos f/

if """ I_ """"""""_ ~ """""" ti

'* """"."""""""- "- """"" *I

I+ Reg= un mdo que contiene un stado final t/

'+-""" "- ""̂ __ .. . */

I * Cmatena dm listas de estados finales *l t.

Edo-f in tune-dos-f in(CEF4CEF2) Edo-fin Wl,tCEF2; r

Edo-f in faux; aux = ~-1; uhile ( aux->sig I = Nu.¡.)

¿UY -- WW-)Sig; aux-)sig : EEF2; return[CEF1);

1

enlista(Lista HLI!jTF,Lista muevo-edo) { Lista *ap; if(rlIST4 =: M U )

else { YISTA = mrwo-do;

ap 2 rCISTA; uhiletap-)sig-tabla != N U L L )

ap = ap->sig-tabla; ap-)siq-tabla = m-edo;

1 1

/* Inicializa las transiciones con @, apartir del gdo inicial de LISTA, crea un nak y almena los valores iniciales qw le corresponden. fJ

It"" """"" "" - */

R.

,f 11

Ir "" """"""_"""" ~

t!

i m t band; Lista t a w ,+localiza( 1; Elemntu *aux2; aun-!ocaliza(&LISTA,Edc); aux2zaux-rsig-nodo;

vhi!@!aux2 1- NUL! && band==O) band=O;

i

aux2m&?-}sig; 1 /* end of while t/

I t Realiza las transicimes con I! y va agregando en una lista !%evl k edos que m alcanzados. Los edos alcanzados se regresan en una llsta [puede 5er va:lai i/

It -"" """"""__""_ """ -" f f

it """ - *I

It Verif ita si dos listas sm 13uales * l

t "

Enl:sta(Edo-fin **teap,lnt valor)

t */

! a """-""" - ""_""""""-""""" ". .. _"" r/

/t ~ - """ ""_""""_ t i

~ """_ ~ """"-"""-"" * ' i

free(aux);

ti

Apartir d~ la i.sta de edos finales en LISTA y la lista de sinbolffi de L-SIflB *l

""""_ "_ f/

.de[ me def m e def me def ¡ne ! M irle

.del me defioe def ¡ne

!dei ine tdef ice rilef ine tdef inE Kief ¡ne :def PIP tdef ine tdef ine

tdr i m e tdef :ne tdef ins trlef ine

' d E f l W

'?Ef i l E

infinito 1t)sr? LIHITE lb3

t,Lpedef struct tabla i int edo; struct nodo tslg-nodo; r-truct tabla 6q-tabla ;

: Lista:

I BIBLIOGRAFIA

-Machines, languajes and computation Denning.

-Introduction to Automata Theory languajes and computation Hopcroft, Ullman.

-Algoritmos y computadoras Trakhtenbrot

-Switching and finite Automata Theory Zvi Kohavi Computer Science Serie.

-Turbo C Reference Guide -Turbo C User's Guide Versión 2.0 Borland International 1 9 8 8 .

-Lenguaje C Introducción a la Programción Kelley/Pohl Ed. Sitesa.

-Lotus 12 3 Graficación en Lotus Ed. Interamericana.

-Flow :hart I1

-Word Versión 4 . 0

Documents

UNIVERBIDAD AUTONOMA METROPOLITANA UNIDAD …