jueves, 26 de septiembre de 2019
miércoles, 25 de septiembre de 2019
martes, 24 de septiembre de 2019
lunes, 23 de septiembre de 2019
viernes, 20 de septiembre de 2019
miércoles, 18 de septiembre de 2019
Automatas de Pila - Investigacion
Los autómatas de pila, en forma similar a como se usan los autómatas finitos, también se pueden utilizar para aceptar cadenas de un lenguaje definido sobre un alfabeto A. Los autómatas de pila pueden aceptar lenguajes que no pueden aceptar los autómatas finitos.
Un autómata de pila cuenta con una cinta de entrada y un mecanismo de control que puede encontrarse en uno de entre un número finito de estados. Uno de estos estados se designa como estado inicial, y además algunos estados se llaman de aceptación o finales. A diferencia de los autómatas finitos, los autómatas de pila cuentan con una memoria auxiliar llamada pila. Los símbolos (llamados símbolos de pila) pueden ser insertados o extraídos de la pila, de acuerdo con el manejo last-in-first-out (LIFO).
Las transiciones entre los estados que ejecutan los autómatas de pila dependen de los símbolos de entrada y de los símbolos de la pila. El autómata acepta una cadena x si la secuencia de transiciones, comenzando en estado inicial y con pila vacía, conduce a un estado final, después de leer toda la cadena x.
La función de transición de estados de un AP puede ser representada por un diagrama donde los nodos representan los estados y los arcos transiciones. Si existe transición tipo (1), el arco queda rotulado de la siguiente manera:
Si el estado actual es ei y la cabeza lectora apunta un símbolo a, y el tope de la pila es X, entonces cambiar al nuevo estado ej, avanzar la cabeza lectora, y sustituir el símbolo del tope X en la pila por la cadena α.
Si α = ZYX deja X , apila Y, y apila Z (nuevo tope Z). donde X, Y, Z ∈ P
Si α =XX deja X y apila X (nuevo tope X).Si α =X deja X como el mismo tope (no altera la pila)
Si α =ε elimina X, y el nuevo tope es el símbolo por debajo (desapila)
jueves, 12 de septiembre de 2019
miércoles, 11 de septiembre de 2019
martes, 10 de septiembre de 2019
viernes, 6 de septiembre de 2019
Comparacion de cadenas de lenguaje - Programa 2
Verificar si las dos cadenas de 8 caracteres pertenecen al mismo lenguaje
Comparacion de cadenas de lenguaje - Programa 1
Verificar si las dos cadenas pertenecen al mismo lenguaje
jueves, 5 de septiembre de 2019
miércoles, 4 de septiembre de 2019
martes, 3 de septiembre de 2019
JFLAP
JFLAP (Java Formal Languages and Automata Package) es un software educativo interactivo escrito en Java para experimentar con temas en el área de ciencias de la computación de lenguajes formales y teoría de autómatas , destinado principalmente para su uso a nivel de pregrado o como tema avanzado para la escuela secundaria. JFLAP permite crear y simular estructuras, como programar una máquina de estados finitos, y experimentar con pruebas, como convertir un autómata finito no determinista (NFA) en un autómata finito determinista (DFA).
JFLAP se desarrolla y mantiene en la Universidad de Duke , con el apoyo de la National Science Foundation desde 1993. Es gratuito y el código fuente de la versión más reciente está disponible, pero con algunas restricciones. JFLAP se ejecuta como una aplicación Java.
Historia
Antes de JFLAP, había varias herramientas de software relacionadas con la teoría de autómatas desarrolladas por Susan H. Rodger y sus alumnos a partir de 1990 en el Departamento de Informática del Instituto Politécnico Rensselaer . En 1992, el primer artículo publicado en un taller de DIMACS 2012 describió una herramienta relacionada llamada NPDA (el artículo fue publicado más tarde en 1994 en una serie DIMACS). NPDA luego evolucionó a FLAP, incluyendo también máquinas de estado finito y máquinas de Turing. En 1993, se publicó un documento sobre el paquete de idiomas formales y autómatas (FLAP). En ese momento, la herramienta fue escrita en C ++ y X Window . Alrededor de 1994, Rodger se mudó a la Universidad de Dukey desarrollo continuo de herramientas. Alrededor de 1996, FLAP se convirtió a Java y el primer artículo mencionado JFLAP se publicó en 1996. En el camino, se desarrollaron otras herramientas como herramientas independientes y luego se integraron en JFLAP. Por ejemplo, un artículo en 1999 describió cómo JFLAP ahora permitía experimentar con pruebas de tipo de construcción, como convertir un NFA en un DFA en un estado mininal DFA, y como otro ejemplo, convertir NPDA en CFG y viceversa. En 2002 JFLAP se convirtió en Swing. En 2005-2007 se realizó un estudio con catorce instituciones que utilizan JFLAP. Un documento sobre este estudio en 2009 mostró que los estudiantes que usaban JFLAP pensaban que JFLAP los hacía sentir más involucrados en la clase y facilitaba el aprendizaje de los conceptos.
La historia de JFLAP está cubierta en el sitio jflap.org e incluye a más de 35 estudiantes del Instituto Politécnico Rensselaer y la Universidad de Duke que han trabajado en JFLAP y herramientas relacionadas desde 1990.
Un artículo de Chakraborty, Saxena y Katti titulado "Cincuenta años de simulación de autómatas: una revisión" en la revista ACM Inroads en diciembre de 2011 declaró lo siguiente sobre JFLAP: "El esfuerzo realizado para desarrollar esta herramienta no tiene paralelo en el campo de la simulación de autómatas. Como resultado, hoy es la herramienta más sofisticada para simular autómatas. Ahora cubre una gran cantidad de temas sobre autómatas y campos relacionados. La herramienta también es la mejor documentada entre las herramientas para simulación de autómatas ". y "La herramienta utiliza gráficos de última generación y es una de las más fáciles de usar. La herramienta es, sin duda, la herramienta más utilizada para la simulación de autómatas desarrollados hasta la fecha. Miles de estudiantes la han utilizado en numerosas universidades en más de cien países."
Temas cubiertos en JFLAP
Los temas sobre lenguaje regular incluyen:
- máquina de estados finitos
- gramática regular
- expresión regular
- Prueba de autómata finito no determinista a determinista autómata finito
- Prueba de autómata finito determinista a gramática regular
- Prueba de autómata finito determinista a expresión regular
- lema de bombeo para idiomas regulares
Los temas sobre lenguaje sin contexto incluyen:
- autómata pushdown
- gramática libre de contexto
- prueba en wikt: autómata pushdown no determinista a gramática libre de contexto
- prueba de gramática libre de contexto para autómata pushdown
- lema de bombeo para un lenguaje sin contexto
- Analizador CYK
- Analizador LL
- Analizador SLR
Temas sobre lenguaje recursivamente enumerable :
- máquina de Turing
- gramática sin restricciones
Otros temas relacionados:
- Máquina Moore
- Máquina de comidas
- Sistema L
lunes, 2 de septiembre de 2019
Suscribirse a:
Entradas (Atom)