Page 24 - Revista FIUDE 2014

Cada transición (como 0 → x, R) indica qué movimiento debe hacer el cabezal si en ese momento se
encuentra en la cinta un símbolo con ese valor.
Si se está procesando la cadena 01#01, se está en el estado S y el cabezal se encuentra sobre el primer 0
en la cinta, la transición 0 → x, R indica que se debe escribir una x en el lugar de la cinta donde estaba el
0, mover el cabezal a la derecha (‘right’ en inglés) y la máquina cambiar de estado, del estado S al T.
El procesar la cadena 01#01 produce los siguientes cambios a nivel del estado actual y del contenido de
la cinta en la máquina de Turing M .
4
De este modo vemos que la cadena 01#01 es
reconocida por la máquina de Turing M .
4
Otras cadenas como 00#11 no serán
reconocidas por la máquina y por lo tanto
no pertenecerán al lenguaje generado por la
máquina (en este caso L ).
4

Conclusiones

La Teoría de Autómatas trata de la definición y propiedades de distintos modelos matemáticos de un
computador tales como los Autómatas Finitos y las Máquinas de Turing u otros modelos que no se han
mencionado como los Autómatas de Pila.
Los lenguajes son conjuntos de cadenas de un determinado alfabeto.
No todos los lenguajes tienen la misma complejidad, algunos lenguajes sencillos pueden ser generados
mediante máquinas como Autómatas Finitos y otros lenguajes más complejos no pueden ser generados
por éstos pues se precisa para reconocerlos, la capacidad de tener una estructura auxiliar de memoria
que permita guardar información de los símbolos ya consumidos o leídos de la cadena que se está
procesando.
Para poder generar estos lenguajes más complejos son necesarios otros tipos de modelo de autómata,
que poseen un mayor poder de generación como son las Máquinas de Turing.

Bibliografía

MICHAEL SIPSER, Introduction to the Theory of Computation 3rd Edition, Editorial Wadsworth
Publishing Co Inc. ISBN : 978-1133187790
CHRISTOS PAPADIMITROU, Elements of the Theory of Computation 2nd Edition, Editorial Prentice-Hall.
ISBN : 978-0132624787

Reflexiones sobre Ingeniería