¿Cuál es el enfoque estándar para minimizar Büchi-Automata (o también Müller-Automata)? Transferir la técnica habitual de palabras finitas, es decir, establecer dos estados para que sean iguales si las palabras "agotándose" de los estados aceptados son las mismas, no funcionará. Por ejemplo,...
Hay un problema abierto en los idiomas formales conocido como el Problema de separación; que se indica brevemente como dadas dos cadenas distintas de longitud , qué tan grande de un DFA se requiere para "separarlas", lo que significa aceptar una cadena pero rechazar la otra.nnn Aquí hay algunos...
Deje que se dé un número . Considere el siguiente lenguaje L n = {nortenn .Lnorte= {w wEl |w ∈ { 0 , 1 }norte}Ln={ww|w∈{0,1}n}L_n = \{ \; ww \; \vert \; w \in \{0,1\}^{n} \; \} En palabras, es el conjunto de cadenas de copia de longitud 2 n .LnorteLnL_n2 n2n2n Considere la siguiente función de...
¿Dónde puedo encontrar una introducción a los autómatas probabilísticos y lo que reconocen (ciertas funciones desde palabras hasta )? ¿Existe un término estándar para tales funciones que son reconocidas por los autómatas probabilísticos, análoga a "lenguajes regulares" para lo que reconocen los...
Se desconoce si o , dondeP⊆CSLP⊆CSLP\subseteq CSLP⊈CSLP⊈CSLP\not\subseteq CSL PPP es el conjunto de todos los idiomas que se pueden decidir en tiempo polinómico en una máquina de Turing determinista, y CSLCSLCSL es la clase de lenguajes sensibles al contexto, conocidos por ser equivalentes a...
Es simple ver que los poderes de 2 sobre el alfabeto {0,1} son regulares porque 10∗10∗10^* es una expresión regular para ello. Pero los poderes de 2 representados en ternario parecen no ser regulares. El bombeo de clases de lema o residuos es difícil de aplicar, ya que parece haber muy poco patrón...
En mi experiencia, los lenguajes sensibles al contexto y los autómatas lineales limitados son frecuentemente omitidos o ignorados en los cursos de teoría de la computabilidad, e incluso quedan fuera de algunos libros de texto notables, aunque los autómatas finitos y pushdown reciben mucha atención....
¿Existen permutaciones y gramática libre de contexto de tamaño polinómico (en ) que describe el lenguaje finito sobre el alfabeto ?π1,π2π1,π2\pi_1,\pi_2|w|=n|w|=n|w|=n{wπ1(w)π2(w)}{wπ1(w)π2(w)}\{w \pi_1(w) \pi_2(w)\}{0,1}{0,1}\{0,1\} ACTUALIZACIÓN: Para una permutación es posible. es la inversión...
Los analizadores de gráficos se pueden implementar según la forma normal de Chomsky o directamente según las reglas de producción. Supongamos por el momento que tenemos un analizador gráfico CYK que usa la forma normal de Chomsky. La binarización no está definida de forma exclusiva. ¿Esto afecta el...
Me preguntaba qué conjuntos de idiomas se generan por restricciones de expresiones regulares. Supongamos que todas las restricciones tienen un símbolo constante para cada elemento de y concatenación. Entonces se pueden formar ocho clases por la presencia o ausencia de complemento / negación,...
Estoy aprendiendo la teoría algebraica del análisis. Mi primer problema es identificar ejemplos de semiring que son específicos de la teoría del lenguaje formal. Aquí hay un intento de construir dos ejemplos. 1 Dada la gramática CNF, los elementos de semiring son conjuntos de símbolos terminales y...
Me gustaría saber por qué para el reconocimiento de lenguajes libres de contexto solo funcionan los autómatas push-down no deterministas (DPA = NPDA). ¿Por qué los autómatas deterministas pushdown (DPDA) no reconocen tales
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
Existen varios modelos diferentes para definir transformaciones entre idiomas. Los transductores de estado finito y las transformaciones de gráficos definibles por MSO sobre gráficos de cadenas son los dos que mejor conozco. Sabemos que los transductores de estado finito de 2 vías (que son más...
¿Cuál es la proporción de CFG ambiguos a todos los CFG ? Como ambos conjuntos son infinitamente contables, la relación no está bien definida. Pero qué pasa con la densidad asintótica : limn↦∞# ambiguous CFG of size<n# CFG of size<nlimn↦∞# ambiguous CFG of size<n# CFG of size<n\lim_{n...
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...
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...
Para un lenguaje libre de contexto determinado G, que llamamos un no terminal nullable si , es decir, podemos derivar la cadena vacía de después de aplicar un número finito de producciones.UNAyoAiA_i UNAyo→∗ϵAi→∗ϵA_i \rightarrow^* \epsilonUNAyoAiA_i Hay un algoritmo simple para determinar qué no...
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...
Considere un lenguaje de expresiones regulares con el cuantificador codicioso , el cuantificador no codicioso ∗ ? , alternancia ordenada y clases de caracteres. (Esto es esencialmente un sublenguaje de PCRE sin referencias posteriores, afirmaciones de búsqueda o algunos de los otros bits más...