Expresiones Regulares

Saludos estudiantes de Teoría de la Computación,

Estas son las referencias prometidas. El material de la Prof. H. Yelitza Contreras, está aquí:

http://webdelprofesor.ula.ve/ingenieria/hyelitza/materias/preteoria/apuntes/tema2.pdf

http://webdelprofesor.ula.ve/ingenieria/hyelitza/materias/preteoria/apuntes/POSIX.pdf

La tesis de la Ing. Yaritza Vargas, está acá:

http://webdelprofesor.ula.ve/ingenieria/jacinto/tesis/2004-tesis-ing-yaritza-vargas.pdf

Allí encontrarán la explicaciones que discutimos, así como los temas que sugerimos para el recuperativo.

El código flex (para Jflex) del analizador léxico de Galatea puede ser visto en línea en (para ejemplos de ER).

http://galatea.svn.sourceforge.net/viewvc/galatea/Galatea/trunk/gCompilerSrc/galatea.flex?revision=482&view=markup

Por último, los ejercicios del parcial anterior y otros están (en formato Jflap) en:

http://webdelprofesor.ula.ve/ingenieria/jacinto/teocomp/p1-pr1.jff
http://webdelprofesor.ula.ve/ingenieria/jacinto/teocomp/p1-pr2.jff
http://webdelprofesor.ula.ve/ingenieria/jacinto/teocomp/mealy.jff
http://webdelprofesor.ula.ve/ingenieria/jacinto/teocomp/hola.jff

Consideren también este código Prolog para generar las expresiones concretas, del que les hablé en clase. No está completo, pero ya les ayudará a generar expresiones con clausura de Kleene.

http://webdelprofesor.ula.ve/ingenieria/jacinto/teocomp/er.pl

--
profundidad(2).

er(A, A) :- A\=[], atomico(A), !.
er((A,R), AR) :- er(A,AA), er(R,RR), er(AA,RR,AR).

er(A+B,[AUB1,AUB2]) :- er(A,AUB1), er(B,AUB2).
er(A^e, E) :-
  profundidad(N), er(A, AA), ere(AA^N, E).

er(A, B, AIB) :- y(A,B,AIB).

ere(_^0, [lambda]). % cualquier expresion cero veces
ere(A^N, [AA|R]) :- % una expresion n veces
  N>0, NN is N-1, ern(N,A,AA), ere(A^NN,R).

ern(1,A,A).
ern(N,A,(A,R)) :-
  N>0, NN is N-1, ern(NN,A,R).
--

Esta es una salida:

?- ereg((0,(1+0)^e), L).
L = (0, 1, 1) ;
L = (0, 1, 0) ;
L = (0, [1, 0], 1) ;
L = (0, 0, 1) ;
L = (0, 0, 0) ;
L = (0, [1, 0], 0) ;
L = (0, 1, 1) ;
L = (0, 1, 0) ;
L = (0, [1, 0], 1) ;
L = (0, 0, 1) ;
L = (0, 0, 0) ;
L = (0, [1, 0], 0) ;
L = (0, 1) ;
L = (0, 0) ;
L = (0, lambda) ;
false.


Nos vemos el lunes.

Buena suerte.