lenguajes formales, gramáticas, teoría de autómatas
He estado revisando Theory of Computation por diversión y esta pregunta me ha estado molestando por un tiempo (curioso, nunca lo pensé cuando aprendí Automata Theory en mi licenciatura). Entonces, ¿por qué exactamente estudiamos autómatas finitos deterministas y no deterministas (DFA / NFA)? Así...
La jerarquía de Chomsky (–Schützenberger) se usa en los libros de texto de informática teórica, pero obviamente solo cubre una fracción muy pequeña de lenguajes formales (REG, CFL, CSL, RE) en comparación con el Diagrama completo del zoológico de complejidad . ¿La jerarquía juega algún papel en la...
Estoy pensando en el siguiente problema: quiero encontrar una expresión regular que coincida con un conjunto particular de cadenas (por ejemplo, direcciones de correo electrónico válidas) y que no coincida con otras (direcciones de correo electrónico no válidas). Supongamos que por expresión...
Las computadoras reales tienen memoria limitada y solo un número finito de estados. Por lo tanto, son esencialmente autómatas finitos. ¿Por qué los informáticos teóricos usan las máquinas de Turing (y otros modelos equivalentes) para estudiar computadoras? ¿Cuál es el punto de estudiar estos...
Siempre hay una forma de aplicación en temas relacionados con la informática teórica. Pero los libros de texto y los cursos de pregrado generalmente no explican la razón por la que la teoría de autómatas es un tema importante y si todavía tiene aplicaciones en la práctica. Por lo tanto, los...
Pregúntele incluso a alguien con experiencia en informática qué es una expresión regular, y es probable que la respuesta vaya más allá de la restricción de estar al alcance de un autómata de estado finito. Por ejemplo, la "expresión regular" /^1?$|^(11+?)\1+$/ creado por la destacada...
Necesito un libro de teoría de autómatas finito con muchos ejemplos que pueda usar para el autoaprendizaje y para prepararme para los
En el prefacio de sus libros muy influyentes Automata, Languages and Machines (Volúmenes A, B), Samuel Eilenberg prometió tentadoramente que los Volúmenes C y D se ocupan de "una jerarquía (llamada la jerarquía racional) de los fenómenos no racionales ... utilizando relaciones racionales como una...
¿El lenguaje { } está libre de contexto o no?unayosijdok El | i≠j,i≠k,j≠k unayosijdok El | yo≠j,yo≠k,j≠ka^{i}b^{j}c^{k} ~|~ i \neq j, i \neq k, j \neq k Me di cuenta de que he encontrado casi todas las variantes de esta pregunta con diferentes condiciones sobre la relación entre i, j y k, pero no...
Es bien sabido que una expresión regular puede ser reconocida por un autómata finito no determinista de tamaño proporcional a la expresión regular, o por un FA determinista que es potencialmente exponencialmente más grande. Además, dada una cadena una expresión regular , la NFA puede probar la...
Arregle un entero nortenn alfabeto Σ = { 0 , 1 }Σ={0,1}\Sigma=\{0,1\} . Defina D FA ( n )DFA(n)DFA(n) como la colección de todos los autómatas de estado finito en nortenn estados con estado inicial 1. Estamos considerando todos los DFA (no solo los conectados, mínimos o no degenerados); por lo...
Como proyecto paralelo, estoy escribiendo un lenguaje usando Python. Comencé usando un clon de flex / bison llamado Ply, pero estoy enfrentando los límites en el poder de lo que puedo expresar con ese estilo de gramática, y no estoy interesado en hackear mi lenguaje debido a un desajuste de...
Me preguntaba si hay un algoritmo `` mejor '' (explicaré en qué sentido) comenzar desde un DFA y construir una expresión regular r tal que L ( A ) = L ( r ) , que la del libro de Hopcroft y Ullman (1979). Allí, los conjuntos R k i j se utilizan para representar conjuntos de cadenas que llevan el...
Considere un autómata finito no determinista y una función f (n) . Además definimos \ Sigma ^ {\ leq k} = \ bigcup_ {i \ leq k} \ Sigma ^ i .A=(Q,Σ,δ,q0,F)A=(Q,Σ,δ,q0,F)A = (Q, \Sigma, \delta, q_0, F)f(n)f(n)f(n)Σ≤k=⋃i≤kΣiΣ≤k=⋃i≤kΣi\Sigma^{\leq k} = \bigcup_{i \leq k} \Sigma^i Ahora analicemos la...
Definimos un lenguaje de árbol regular como en el libro TATA : es el conjunto de árboles aceptado por un autómata de árbol finito no determinista (Capítulo 1) o, de manera equivalente, el conjunto de árboles generado por una gramática de árbol regular (Capítulo 2). Ambos formalismos se parecen...
Dado un lenguaje regular (NFA, DFA, gramática o expresión regular), ¿cómo se puede contar el número de palabras aceptadas en un idioma determinado? Tanto "con exactamente n letras" como "con como máximo n letras" son de interés. Margareta Ackerman tiene dos documentos sobre el tema relacionado de...
En muchos artículos que involucran gramáticas libres de contexto (CFG), los ejemplos de tales gramáticas presentados allí a menudo admiten caracterizaciones fáciles del lenguaje que generan. Por ejemplo: S→aaSbS→aaSbS \to a a S b S→S→S \to genera {a2ibi|i≥0}{a2ibi|i≥0}\{ a^{2i} b^i | i \geq...
1) ¿Cuál es, si la hay, la relación entre la escritura estática y las gramáticas formales? 2) En particular, ¿sería posible que un autómata lineal limitado verificara si, por ejemplo, un programa C ++ o SML estaba bien escrito? ¿Un autómata apilado anidado? 3) ¿Existe una forma natural de...
Hace poco estuve leyendo sobre el analizador Earley y creo que es uno de los algoritmos más elegantes que he visto hasta la fecha. Sin embargo, el algoritmo en su sentido tradicional es un reconocedor y no un analizador, lo que significa que puede detectar si una cadena coincide con un CFG...
Para cualquier lenguaje sobre Σ * , definir L 1 / 2 = { x ∈ Σ * : x y ∈ L , y ∈ Σ | x | } . En palabras, consiste de todas las para los cuales existe un de igual longitud tal que .LLLΣ∗Σ∗\Sigma^*L1/ 2= { x ∈ Σ∗: x y∈ L , y∈ ΣEl | x |} .L1/ /2={X∈Σ∗:Xy∈L,y∈ΣEl |XEl |}.L_{1/2} = \{x \in \Sigma^* :...