Teoría de autómatas, que incluye máquinas abstractas, gramáticas, análisis, inferencia gramatical, transductores y técnicas de estado finito
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...
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...
Hace poco escuché esto "Una máquina no determinista no es lo mismo que una máquina probabilística. En términos generales, una máquina no determinista es una máquina probabilística en la que no se conocen las probabilidades de transiciones". Siento como si entendiera el punto, pero realmente no....
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...
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...
¿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...
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...
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...
No puedo pensar en ningún modelo de este tipo, ¿tal vez alguna forma de cálculo lambda mecanografiado? algún autómata celular elemental? Esto casi refutaría el "Principio de equivalencia computacional" de Wolfram: Casi todos los procesos que obviamente no son simples pueden verse como cálculos...
La intersección de dos (mínimos) DFA con n estados se puede calcular utilizando O (n 2 ) tiempo y espacio. Esto es óptimo en general, ya que el DFA resultante (mínimo) puede tener n 2 estados. Sin embargo, si el DFA mínimo resultante tiene estados z, donde z = O (n), ¿se puede calcular en el...
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...
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^* :...
Dadas dos cadenas x e y, quiero construir un DFA de tamaño mínimo que acepte x y rechace y. Una forma de hacerlo es la búsqueda de fuerza bruta. Enumera los DFA que comienzan con los más pequeños. Intenta cada DFA hasta que encuentre uno que acepte x y rechace y. Quiero saber si hay alguna otra...
Para un alfabeto finito fijo , un lenguaje formal sobre es normal si existe un autómata finito determinista (DFA) sobre que acepta exactamente .L Σ Σ LΣΣ\SigmaLLLΣΣ\SigmaΣΣ\SigmaLLL Me interesan los idiomas que son "casi" regulares en el sentido de que pueden ser reconocidos por las familias de...
Deje que sean dos lenguajes regulares dados por NFA M 1 , M 2 como entrada.L1, L2L1,L2L_1,L_2METRO1, M2M1,M2M_1,M_2 Supongamos que nos gustaría verificar si . Esto puede hacerse claramente mediante un algoritmo cuadrático que computa el autómata del producto de M 1 , M 2 , pero me preguntaba si se...