luio

Redalyc
Sistema de Información Científica
Red de Revistas Científicas de América Latina, el Caribe, España y Portugal

OROZCO GUTIÉRREZ, ÁLVARO ANGEL; HOLGUÍN LONDOÑO, MAURICIO
DESARROLLO DE UN ENTORNO DE SIMULACIÓN PARA AUTÓMATAS
DETERMINISTAS
Scientia Et Technica, vol. XV, núm. 42, agosto, 2009, pp. 17-22
Universidad Tecnológica de Pereira
Pereira, Colombia
Disponible en:http://redalyc.uaemex.mx/src/inicio/ArtPdfRed.jsp?iCve=84916714005

Scientia Et Technica
ISSN (Versión impresa): 0122-1701
scientia@utp.edu.co
Universidad Tecnológica de Pereira
Colombia

¿Cómo citar?

Número completo

Más información del artículo

Página de la revista

www.redalyc.org
Proyecto académico sin fines de lucro, desarrollado bajo la iniciativa de acceso abierto

Scientia etTechnica Año XV, No 42 Agosto de 2009. Universidad Tecnológica de Pereira. ISSN 0122-1701

17

DESARROLLO DE UN ENTORNO DE SIMULACIÓN PARA AUTÓMATAS
DETERMINISTAS
Development of a simulation environment for deterministic automatas

RESUMEN
Se muestra el poderío matemático y generalidad de la Máquina de Turing entre
las máquinas abstractas equivalentes a la jerarquía de lenguajes formalesque
desarrolló Noam Chomsky en su obra Teoría de las Gramáticas
Transformacionales, por medio del desarrollo de un simulador de autómatas; que
permite representar el funcionamiento de un reconocedor de lenguajes que
determina si una palabra, cadena finita de símbolos de un alfabeto, pertenece o
no a un lenguaje dado. Se enmarca como herramienta pedagógica que permite
mostrar la generalidad dela máquina de Turing al abarcar el conjunto de los
autómatas finitos y de pila.
PALABRAS CLAVES: Autómatas, Máquina de Estados Finitos, Máquina de
Turing.
ABSTRACT
It shows the mathematics power and generality of Turing Machine respect to
abstract machines equivalents to the hierarchy of formal languages developed
by Noam Chomsky in his book Theory of Transformational Grammars, bydeveloping a automata simulator, which allows represent the behavior of a
language recognizer that determines whether a word, string of symbols from a
finite alphabet, belongs to a given language. It is framed as a teaching tool that
shows the generality of the Turing Machine to cover all of the finite automatas
and push down machines.

ÁLVARO ANGEL OROZCO
GUTIÉRREZ
Doctor en BioingenieríaDirector Grupo de Investigación en
Control e Instrumentación
Profesor Titular
Universidad Tecnológica de Pereira
aaog@utp.edu.co
MAURICIO
HOLGUÍN
LONDOÑO
Ingeniero Electricista, M.Sc (C)
Profesor Transitorio
Estudiante Maestría en Ingeniería
Eléctrica.
Universidad Tecnológica de Pereira
ma_hol@ohm.utp.edu.co

KEYWORDS: Automatas, Finite State Machine, Turing Machine.

1. INTRODUCCIÓNTuring propuso en los años treinta un modelo de máquina
abstracta [1], como una extensión de los autómatas
finitos, que resultó ser de una gran simplicidad y poderío
a la vez. La máquina de Turing es particularmente
importante porque es la más poderosa de todas las
máquinas abstractas conocidas.
Se ha tratado de encontrar otros modelos de máquinas o
formalismos que posean una mayorgeneralización que
las Maquinas de Turing, en el mismo sentido que las
Máquinas de Turing son más generales que los
Autómatas Finitos y los Autómatas de Pila [2]; (se dice
que un tipo de máquina MA tiene una mayor generalidad
que un tipo MB cuando el conjunto de lenguajes
aceptados por alguna máquina en MB es un subconjunto
propio de los aceptados por MA), pero todos los intentos
han sidoinfructuosos al encontrar que dichas extensiones
son equivalentes en poder de cálculo a la Máquina de
Turing original [3]; muchas de estas extensiones dotan de
mayor flexibilidad al diseño de una Máquina de Turing
que resuelve un problema en particular.
Fecha de Recepción: 8 de julio de 2009
Fecha de Aceptación: 13 de Agosto de 2009

A. Turing propuso, en su llamada Tesis de Turing, que la...