Automata De Pila
Páginas: 8 (1804 palabras)
Publicado: 12 de agosto de 2012
INDICE
Introducción…………………………………………………………………………………………………….3
Objetivos………………………………………………………………………………………………………….4
Autómata…………………………………….…………………………………………………………………..5
Definición de un Autómata de Pila …………………….……………………………………………6
Características………………..…………………………………………………………………….……..…..6 Y 7
Principio de análisis……………………………………….……………………………………….…………7
Formalización de losautómatas de pila……………………………………………..….………….8
Funcionamiento…………………………………………………………….………………..……….…..…..9
Proceso de reconocimiento de una cadena………………….…………………..……….…....10
tipos de problemas a los que se aplican…………………………………………………….……..10
Ejemplos…………………………………………………………………………………………….…………….11
Conclusiones……………………………………………………………………………………………….……14
introducción
Un autómata a pila es undispositivo que tiene acceso a Una secuencia de símbolos de entrada, que en general se representa por una cinta que se desplaza frente a un mecanismo de captación de dichos símbolos De igual manera que los lenguajes regulares se pueden representar mediante autómatas finitos deterministas, los lenguajes independientes del contexto tienen su correspondencia en otro tipo de dispositivo: el Autómata a Pila(AP).
Objetivos:
Objetivo general
Al termino de esta presentación se contará con la capacidad de
Identificar los autómatas de pila y sus diferentes tipos, así como los
lenguajes independientes de contexto.
Objetivo específicos
* Conocer sobre la importancia de los autómatas de pila conocer todos los símbolos y los lenguajes relacionados con los autómatas de pilas.
* Entenderen realidad las importancias que tienen los autómatas de pilas y todo su funcionamiento.
Autómata
Al igual que con los lenguajes regulares podemos definir un autómata como una máquina reconocedora de cadenas palabras) de un determinado lenguaje.
Los autómatas son dispositivos de cómputo que operan como una máquina de estados finitos, las cuales realizan un encadenamiento automático ycontinuo de operaciones capaces de procesar una información de entrada para producir otra de salida.
Por lo general los autómatas finitos no son lo suficientemente poderosos para aceptar el control de enlace lógico LLC (Logical Link Control) quien es el que define la forma en que los datos son transferidos sobre el medio físico, proporcionando servicio a las capas superiores La idea es agregar“algo” al os Autómatas Finitos para que de alguna manera se incremente.
Por tal motivo surgen los Autómatas de Pila, que al igual que un Autómata Finito, cuenta con un flujo de entrada y un flujo de control que puede encontrarse en uno de entre un número finito de estados
Uno de estos estados se designa como el inicial y por lo menos un estado de aceptación
La principal diferencia es que losAutómatas de pila cuentan justamente con una pila en donde se puede almacenar información para recuperarla más tarde.
Los símbolos que pueden almacenarse en esta pila se conocen como símbolos de pila de la maquina, constituyen un conjunto finito que puede incluir algunos símbolos definiendo el alfabeto de la maquina y quizá algunos símbolos adicionales que se utilizan como marcas internas.
Siuna maquina inserta un símbolo especial en la pila antes de efectuar algún otro cálculo, entonces ese símbolo en la cima de la pila puede usarse como indicador de pila vacía para cálculos posteriores, dicho símbolo es #.
Definición
Un autómata con pila, autómata a pila o autómata de pila es un modelo matemático de un sistema que recibe una cadena constituida por símbolos de un alfabeto ydetermina si esa cadena pertenece al lenguaje que el autómata reconoce. El lenguaje que reconoce un autómata con pila pertenece al grupo de los lenguajes libres de contexto en la clasificación de la Jerarquía de Chomsky.
Características
Un autómata de pila (SA, en inglés stack automata) es un PDA con las siguientes dos características:
1.- La entrada es de dos direcciones, se encuentra en...
Introducción…………………………………………………………………………………………………….3
Objetivos………………………………………………………………………………………………………….4
Autómata…………………………………….…………………………………………………………………..5
Definición de un Autómata de Pila …………………….……………………………………………6
Características………………..…………………………………………………………………….……..…..6 Y 7
Principio de análisis……………………………………….……………………………………….…………7
Formalización de losautómatas de pila……………………………………………..….………….8
Funcionamiento…………………………………………………………….………………..……….…..…..9
Proceso de reconocimiento de una cadena………………….…………………..……….…....10
tipos de problemas a los que se aplican…………………………………………………….……..10
Ejemplos…………………………………………………………………………………………….…………….11
Conclusiones……………………………………………………………………………………………….……14
introducción
Un autómata a pila es undispositivo que tiene acceso a Una secuencia de símbolos de entrada, que en general se representa por una cinta que se desplaza frente a un mecanismo de captación de dichos símbolos De igual manera que los lenguajes regulares se pueden representar mediante autómatas finitos deterministas, los lenguajes independientes del contexto tienen su correspondencia en otro tipo de dispositivo: el Autómata a Pila(AP).
Objetivos:
Objetivo general
Al termino de esta presentación se contará con la capacidad de
Identificar los autómatas de pila y sus diferentes tipos, así como los
lenguajes independientes de contexto.
Objetivo específicos
* Conocer sobre la importancia de los autómatas de pila conocer todos los símbolos y los lenguajes relacionados con los autómatas de pilas.
* Entenderen realidad las importancias que tienen los autómatas de pilas y todo su funcionamiento.
Autómata
Al igual que con los lenguajes regulares podemos definir un autómata como una máquina reconocedora de cadenas palabras) de un determinado lenguaje.
Los autómatas son dispositivos de cómputo que operan como una máquina de estados finitos, las cuales realizan un encadenamiento automático ycontinuo de operaciones capaces de procesar una información de entrada para producir otra de salida.
Por lo general los autómatas finitos no son lo suficientemente poderosos para aceptar el control de enlace lógico LLC (Logical Link Control) quien es el que define la forma en que los datos son transferidos sobre el medio físico, proporcionando servicio a las capas superiores La idea es agregar“algo” al os Autómatas Finitos para que de alguna manera se incremente.
Por tal motivo surgen los Autómatas de Pila, que al igual que un Autómata Finito, cuenta con un flujo de entrada y un flujo de control que puede encontrarse en uno de entre un número finito de estados
Uno de estos estados se designa como el inicial y por lo menos un estado de aceptación
La principal diferencia es que losAutómatas de pila cuentan justamente con una pila en donde se puede almacenar información para recuperarla más tarde.
Los símbolos que pueden almacenarse en esta pila se conocen como símbolos de pila de la maquina, constituyen un conjunto finito que puede incluir algunos símbolos definiendo el alfabeto de la maquina y quizá algunos símbolos adicionales que se utilizan como marcas internas.
Siuna maquina inserta un símbolo especial en la pila antes de efectuar algún otro cálculo, entonces ese símbolo en la cima de la pila puede usarse como indicador de pila vacía para cálculos posteriores, dicho símbolo es #.
Definición
Un autómata con pila, autómata a pila o autómata de pila es un modelo matemático de un sistema que recibe una cadena constituida por símbolos de un alfabeto ydetermina si esa cadena pertenece al lenguaje que el autómata reconoce. El lenguaje que reconoce un autómata con pila pertenece al grupo de los lenguajes libres de contexto en la clasificación de la Jerarquía de Chomsky.
Características
Un autómata de pila (SA, en inglés stack automata) es un PDA con las siguientes dos características:
1.- La entrada es de dos direcciones, se encuentra en...
Leer documento completo
Regístrate para leer el documento completo.