un tiempo he sentido curiosidad por las máquinas de Turing con exactamente una cinta y exactamente 3 estados (es decir, el estado inicial , el estado de aceptación y el estado de rechazo ). Tenga en cuenta que permito alfabetos de cinta arbitrarios (finitos) (es decir, el alfabeto de cinta no está...
Deje ser un alfabeto finito. Para un lenguaje dado el monoide sintáctico es una noción bien conocida en la teoría del lenguaje formal. Además, un monoide reconoce un lenguaje si existe un morfismo tal que .AAAL⊆A∗L⊆A∗L \subseteq A^{\ast} M(L)M(L)M(L)MMMLLLφ:A∗→Mφ:A∗→M\varphi : A^{\ast} \to...
Si hay algunos resultados en la resolución de problemas de idiomas formales utilizando análisis matemáticos, matemáticas continuas. Por ejemplo, resolver el problema de la intersección del no vacío para un lenguaje libre de contexto y un lenguaje
Estoy buscando escribir una encuesta sobre el método de representar la dinámica de la computación basada en el estado en el marco de las coalgebras. Hasta ahora, he logrado encontrar documentos sobre representaciones de coalgebra de DFA, NFA, máquinas Mealy, máquinas Moore, gramáticas libres de...
Sabemos que todos los autómatas push down son representables utilizando gramáticas libres de contexto. Además, existe un algoritmo para construir un CFG a partir de cualquier PDA (por ejemplo, la prueba de Sipser introducida a la teoría de la computación). ¿Hay alguna herramienta que haga esta...
Escriba como el mapa Parikh --es decir, , donde es el número de veces que aparece en . Es bien sabido que, para un CFL , es un conjunto semilineal (este es el teorema de Parikh). Se conocen otras cosas interesantes, pero no he encontrado nada sobre el mapa Parikh de un lenguaje sensible al...
Estoy escribiendo un modelo de juguete , y estoy en el punto en que es hora de implementar la traducción de autómatas LTL a Buchi. Por una variedad de razones obvias, deseo que el algoritmo sea simple :) por ejemplo, quiero que el código permanezca extremadamente claro y conciso durante el mayor...
Estoy tratando de aclarar mi comprensión en el ejemplo presentado en la Sección 2.2 de Autómatas cuánticos finitos de 1 vía: fortalezas, debilidades y generalizaciones (este enlace alternativo también puede ser útil). Este ejemplo proporciona un ejemplo muy simplificado de un 1-QFA con las...
Relacionado con una pregunta reciente ( Límites en el tamaño del NFA más pequeño para L_k-distinct ) Noam Nisan solicitó un método para proporcionar un límite inferior mejor para el tamaño de un NFA que el que obtenemos de los límites de complejidad de la comunicación. Lo que sigue es una versión...
Dado un NFA NnorteN y su DFA equivalente que DreDresulta de la determinación total de NnorteN (usando la construcción del conjunto de potencia, por ejemplo), las siguientes propiedades se mantienen para NnorteN , DreD y para cualquier palabra www : lee w en tiempo de ejecución como máximo O ( |...
La conjetura de Cerny es la afirmación de que cualquier autómata de sincronización con nnn estados tiene una palabra de longitud de sincronización como máximo (n−1)2(n−1)2(n-1)^2 . El mejor límite superior actual para la longitud de una palabra de sincronización es O(n3)O(n3)O(n^3) . Digamos que...