Preguntas etiquetadas con fl.formal-languages

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...

Un estudiante me pidió lo siguiente y no pude encontrar una respuesta completa: ¿Existen propiedades de cierre para la clase de idiomas que no están libres de contexto? Es bastante fácil encontrar ejemplos que muestren que no está cerrado bajo intersección e iteración (operador estrella de...

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...

¿Se sabe algo sobre lenguajes reconocidos por un autómata determinista bidireccional de múltiples cabezas o un logspace TM con contador (modelo equivalente)? Esta clase se llama Aux2DC en el documento de mi asesor . ¿O sobre tal clase no determinista? He obtenido que la clase de idiomas reconocidos...

En mi trabajo surgió el problema de la clasificación CFL bajo imágenes de funciones racionales. En otros términos, ¿qué clase de lenguajes forman idiomas , para el contexto fijo lenguaje libre y el transductor de estados finitos determinista . He obtenido algunos resultados fáciles, como el...

Estaba leyendo sobre el problema de la altura de las estrellas y noté que la familia de expresiones regulares de Eggan sigue un patrón simple que puede describirse mediante una expresión regular. Mi pregunta es: ¿hay resultados interesantes sobre expresiones regulares que describan familias de...

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...

Estoy confundido sobre el ejemplo dado en el artículo de Wikipedia sobre gramática sensible al contexto: https://en.wikipedia.org/wiki/Context-sensitive_grammar Descargo de responsabilidad : ya he cambiado la sección discutida en el artículo de Wikipedia, por lo que el estado actual del artículo...

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...