Automatas
Páginas: 7 (1596 palabras)
Publicado: 18 de abril de 2012
¿Qué otros autómatas existen?
¿What other automata exist?
Resumen— La teoría de autómatas es una rama de las ciencias de la computación que estudia las máquinas abstractas y los problemas que éstas son capaces de resolver. La teoría de autómatas está estrechamente relacionada con la teoría del lenguaje formal ya que los autómatas son clasificados a menudo por la clase de lenguajesformales que son capaces de reconocer. Existen autómatas útiles para especificar el comportamiento de hardware, sistemas operativos y sistemas de control, otros en el modelo simple de arquitectura de computadores, lenguajes de programación, algoritmos; generando una variedad de aplicaciones fructíferas en el campo de la teoría computacional.
Palabras clave— autómata, aceptación, concatenación,determinismo, estado, lenguaje, maquina, parámetros, símbolos, transición.
Abstract— Automata theory is a branch of computer science that studies the abstract machines and problems they are able to resolve. Automata theory is closely related to formal language theory as the automata are often classified by the class of formal languages that are able to recognize. Automata are useful forspecifying the behavior of hardware, operating systems and control systems, others in the simple model of computer architecture, programming languages, algorithms, generating a variety of successful applications in the field of computational theory.
Key Word — automaton, acceptance, concatenation, determinism, state, language, machine, parameters, symbols, transition.INTRODUCCIÓN
La computación, muy avanzada hoy en día, sienta sus bases sobre una sólida plataforma desarrollada con mucho esfuerzo e investigación, un área importante es el trabajo con los lenguajes de programación, cuyas raíces están en la teoría de autómatas y lenguajes formales. Dentro del proceso académico universitario se alcanza a comprender aspectos básicos sobre la teoría de autómatas, conociendodiferentes tipos de maquinas y sus aplicaciones en la informática; pero surge una incógnita ¿existen otros autómatas? Solo se puede saber la repuesta después de una exhaustiva investigación. Descubriendo nuevas maquinas que reconocen lenguajes y generan gramáticas, produciendo aplicabilidades al mundo de la computación.
CONTENIDO
II.I ω-autómatas
En la teoría deautómatas , una rama de la ciencia de la computación teórica , un autómata es una variación del autómata finito que se ejecuta en cadenas infinitas, en lugar de lo finito, como entrada. Los ω-autómatas tienen una variedad de condiciones de aceptación y no simplemente un conjunto de estados de aceptación.
Los ω-autómatas son útiles para especificar el comportamiento de los sistemas que no seespera de terminar, tales como hardware, sistemas operativos y sistemas de control .
II.I.I Clases de ω-autómatas:
Autómatas de Büchi , autómatas Rabin, autómatas Streett, autómatas paridad y autómatas Muller, Estas clases de ω-autómatas difieren sólo en términos de condición de aceptación . Todos ellos reconocen precisamente los ω-lenguajes regulares, excepto para el autómata deterministade Büchi, que es estrictamente más débil que todos los demás. A pesar de todo, estos autómatas reconocen el mismo conjunto de ω-lenguajes, que sin embargo, difieren en la concisión de la representación de un determinado ω-lenguaje.
Formalmente, un ω-autómata determinista es una tupla A = (Q, Σ, δ, q 0, Acc) que consta de los siguientes componentes:
• Q: es un conjunto finito . Loselementos de Q se denominan los estados de A.
• Σ: es un conjunto finito llamado el alfabeto de la A.
• δ: Q x Σ → Q es una función, llamada la función de transición de A.
• q 0: es un elemento de Q, llamado el estado inicial.
• El CAC: es la condición de aceptación, formalmente un subconjunto de Q ω.
II.II Autómatas de cola
Una máquina de cola es un autómata de máquina de...
¿What other automata exist?
Resumen— La teoría de autómatas es una rama de las ciencias de la computación que estudia las máquinas abstractas y los problemas que éstas son capaces de resolver. La teoría de autómatas está estrechamente relacionada con la teoría del lenguaje formal ya que los autómatas son clasificados a menudo por la clase de lenguajesformales que son capaces de reconocer. Existen autómatas útiles para especificar el comportamiento de hardware, sistemas operativos y sistemas de control, otros en el modelo simple de arquitectura de computadores, lenguajes de programación, algoritmos; generando una variedad de aplicaciones fructíferas en el campo de la teoría computacional.
Palabras clave— autómata, aceptación, concatenación,determinismo, estado, lenguaje, maquina, parámetros, símbolos, transición.
Abstract— Automata theory is a branch of computer science that studies the abstract machines and problems they are able to resolve. Automata theory is closely related to formal language theory as the automata are often classified by the class of formal languages that are able to recognize. Automata are useful forspecifying the behavior of hardware, operating systems and control systems, others in the simple model of computer architecture, programming languages, algorithms, generating a variety of successful applications in the field of computational theory.
Key Word — automaton, acceptance, concatenation, determinism, state, language, machine, parameters, symbols, transition.INTRODUCCIÓN
La computación, muy avanzada hoy en día, sienta sus bases sobre una sólida plataforma desarrollada con mucho esfuerzo e investigación, un área importante es el trabajo con los lenguajes de programación, cuyas raíces están en la teoría de autómatas y lenguajes formales. Dentro del proceso académico universitario se alcanza a comprender aspectos básicos sobre la teoría de autómatas, conociendodiferentes tipos de maquinas y sus aplicaciones en la informática; pero surge una incógnita ¿existen otros autómatas? Solo se puede saber la repuesta después de una exhaustiva investigación. Descubriendo nuevas maquinas que reconocen lenguajes y generan gramáticas, produciendo aplicabilidades al mundo de la computación.
CONTENIDO
II.I ω-autómatas
En la teoría deautómatas , una rama de la ciencia de la computación teórica , un autómata es una variación del autómata finito que se ejecuta en cadenas infinitas, en lugar de lo finito, como entrada. Los ω-autómatas tienen una variedad de condiciones de aceptación y no simplemente un conjunto de estados de aceptación.
Los ω-autómatas son útiles para especificar el comportamiento de los sistemas que no seespera de terminar, tales como hardware, sistemas operativos y sistemas de control .
II.I.I Clases de ω-autómatas:
Autómatas de Büchi , autómatas Rabin, autómatas Streett, autómatas paridad y autómatas Muller, Estas clases de ω-autómatas difieren sólo en términos de condición de aceptación . Todos ellos reconocen precisamente los ω-lenguajes regulares, excepto para el autómata deterministade Büchi, que es estrictamente más débil que todos los demás. A pesar de todo, estos autómatas reconocen el mismo conjunto de ω-lenguajes, que sin embargo, difieren en la concisión de la representación de un determinado ω-lenguaje.
Formalmente, un ω-autómata determinista es una tupla A = (Q, Σ, δ, q 0, Acc) que consta de los siguientes componentes:
• Q: es un conjunto finito . Loselementos de Q se denominan los estados de A.
• Σ: es un conjunto finito llamado el alfabeto de la A.
• δ: Q x Σ → Q es una función, llamada la función de transición de A.
• q 0: es un elemento de Q, llamado el estado inicial.
• El CAC: es la condición de aceptación, formalmente un subconjunto de Q ω.
II.II Autómatas de cola
Una máquina de cola es un autómata de máquina de...
Leer documento completo
Regístrate para leer el documento completo.