[Todos CMAT] Coloquio de Estudiantes

Joaquin Lema joalema1123 en gmail.com
Mar Nov 7 23:45:52 -03 2017


Buenas a todos.

Este *jueves* 9/11 a las* 18:15* hs en el salón de seminarios del 14
escucharemos a *Damián Ferencz*. Abajo va el título y el resumen.

Los esperamos!

======================================================
*Equivalencia entre Autómatas Finitos y Lenguajes Regulares*

En el marco de la Teoría de la Computación, el modelo de los automatas
finitos constituye uno de los modelos mas básicos, y tiene como motivación
inicial la de representar matemáticamente a las maquinas de estado finito,
sistemas lógicos presentes en el diseño interno de muchos aparatos
eléctricos simples, tales como electrodomésticos, ascensores, etc.

En una de sus variantes (así como sucede con paradigmas mas complejos, como
los autómatas con pila y maquinas de Turing), los autómatas finitos pueden
presentarse como reconocedores de lenguajes. [En esta presentación, el
autómata es una caja donde puedo colocar una cinta grabada con una palabra,
y se enciende una luz verde cuando termina de leerla o una luz roja]. Lo
que veremos es que la clase de lenguajes decidibles por un autómata finito
puede caracterizarse de una forma muy precisa como los lenguajes de
expresiones regulares. Para probar esto, nos apoyaremos en dos
construcciones sencillas, el autómata producto y el autómata finito no
determinista.

Si da el tiempo, podríamos charlar sobre los autómatas con pila (stack), y
ver como la clase de lenguajes reconocibles aumenta considerablemente. De
hecho, es el primer escalón dentro de la Jerarquía de Chomsky para
gramáticas formales.
======================================================
------------ próxima parte ------------
Se ha borrado un adjunto en formato HTML...
URL: <http://listas.cmat.edu.uy/pipermail/todos/attachments/20171107/c6fa5cae/attachment.html>


Más información sobre la lista de distribución Todos