automatas

LENGUAJES FORMALES
Y
AUTOMATAS

Incluye Redes de Petri

Dr. Ramon Brena Pinero
Centro de Inteligencia Arti cial
Instituto Tecnologico y de Estudios Superiores
de Monterrey Campus Monterrey
Enero de 1997

ii

b a a b a b

q0
q1

q7

q2

q6
q5

q3
q4

iii

Prefacio
En a~os reciente se ha visto la aparicion de un buen numero de textos en el tema de Lenguajes
nFormales y Automatas (Ver al nal referencias 5], 3], 10], 4], 2], etc.). Por una parte, esto
indica la importancia y riqueza que el tema tiene por otra, ante tal variedad de oferta todo
nuevo libro en el area requiere una justi cacion, un aporte con respecto a lo existente.
Este texto se situa en una generacion de textos que tratan de poner el estudio de los
lenguajes formales y aotomatas alalcance de estudiantes que no necesariamente son avezados matematicos buscando establecer nuevos teoremas, sino que buscan una iniciacion a
estos temas, que ademas les sirva como un ejercicio en el arte de formalizar, en particular en
nociones relacionadas con la computacion. Entre estos textos \accesibles", encontramos, por
ejemplo, a 10]. Estos nuevos textos han reemplazado en muchasuniversidades a los \clasicos" 3] y aun 5] -que ya era mas accesible-, y han permitido que la teor a de la computacion
se estudie a nivel profesional en carreras relacionadas con computacion y matematicas.
El presente libro es resultado de una experiencia de impartir el curso de Teor a de la
Computacion por mas de 10 semestres en el ITESM, Monterrey. Durante este lapso, aunque
ciertamente se fueenriqueciendo el contenido tecnico, el principal re namiento consistio en
ir detectando cuidadosamente las di cultades principales a las que se enfrentaban los estudiantes, para poder estructurar y presentar el material de forma que aquellos estuvieran en
condiciones de \digerirlo" de manera constructiva. Aqui el enfasis no es tanto en hacer el
curso \mas facil" para el estudiante, sino en darle loselementos para ser mas e caz como
aprendiz. La teor a educativa que sustenta esta forma de trabajo es la del \andamiaje", que,
como el nombre sugiere, provee al estudiante una estructura de apoyo para que el mismo
vaya reconstruyendo en su cabeza la red de conceptos y relaciones que caracterizan al area.
Este texto es aplicable tanto al nivel de maestr a en computacion o equivalente, como aclases de nivel profesional (licenciaturas, ingenier as). De hecho en el ITESM se ha aplicado
en ambos niveles. Las secciones cuyo nivel es propiamente de maestr a son identi cadas por
medio de un signo \ ".
En breve, los puntos que caracterizan a este libro, y que en cierta medida lo hacen
particular, son:
La presentacion didactica ha sido -en nuestra opinion- mas pulida que en la mayor a
detextos en Teor a de la Computacion.
Se cubre el tema de las Redes de Petri, tema ntimamente relacionado con los automatas, y que ha adquirido una gran importancia en aplicaciones de manufactura, Sistemas
Operativos y otras areas.
Los algoritmos no se presentan en forma de \seudocodigo", es decir, usando estructuras
de control de lenguajes imperativos (p.ej. while, for, etc.), sino que se tratade dar una

iv
interpretacion intuitiva de los resultados intermedios obtenidos por los algoritmos. En
efecto, opinamos que el codigo y seudocodigo estan bien para ser entendidos por un
compilador, pero no por un humano.
bb < contexto2 >
Podemos ver que en esta expresion aparecen directamente las bb que deben estar en la ER,
rodeadas por otras dos ER, que son < contexto1 > y < contexto2.Ahora el problema es
determinar que ER corresponden a < contexto1 > y < contexto2 >, lo cual es un subproblema
del problema original. El lenguaje de < contexto1 > comprende a las palabras en que toda b
esta seguida de una a o una c. Esta ER es facil de obtener directamente, y es (ba + bc + a + c) .
Similarmente se puede obtener la expresion para < contexto2 >, que es (a + c + ab + cb) ,
por...