Ecuación del lenguaje

Las ecuaciones de lenguaje son enunciados matemáticos que se parecen a las ecuaciones numéricas , pero las variables asumen valores de lenguajes formales en lugar de números. En lugar de operaciones aritméticas en ecuaciones numéricas, las variables se unen mediante operaciones de lenguaje. Entre las operaciones más comunes en dos lenguajes A y B están la unión de conjuntos A ∪ B , la intersección de conjuntos A ∩ B y la concatenación A ⋅ B . Finalmente, como una operación que toma un solo operando , el conjunto A ^* denota la estrella de Kleene del lenguaje A . Por lo tanto, las ecuaciones de lenguaje pueden usarse para representar gramáticas formales , ya que los lenguajes generados por la gramática deben ser la solución de un sistema de ecuaciones de lenguaje.

Ecuaciones del lenguaje y gramáticas libres de contexto

Ginsburg y Rice ^[1] dieron una definición alternativa de gramáticas libres de contexto mediante ecuaciones de lenguaje. A cada gramática libre de contexto , se le asocia un sistema de ecuaciones en variables . Cada variable es una incógnita del lenguaje y se define mediante la ecuación donde , ..., son todas producciones para . Ginsburg y Rice utilizaron un argumento de iteración de punto fijo para mostrar que siempre existe una solución, y demostraron que la asignación es la solución mínima para este sistema, ^{[ aclarar ]} es decir, cualquier otra solución debe ser un subconjunto ^{[ aclarar ]} de esta. ${\displaystyle G=(V,\Sigma ,R,S)}$ ${\displaystyle V}$ ${\displaystyle X\in V}$ ${\displaystyle \Sigma }$ ${\displaystyle X=\alpha _{1}\cup \ldots \cup \alpha _{m}}$ ${\displaystyle X\to \alpha _{1}}$ ${\displaystyle X\to \alpha _{m}}$ ${\displaystyle X}$ ${\displaystyle X=L_{G}(X)}$

Por ejemplo, la gramática corresponde al sistema de ecuaciones que tiene como solución todo superconjunto de . ${\displaystyle S\to aSc\mid b\mid S}$ ${\displaystyle S=(\{a\}\cdot S\cdot \{c\})\cup \{b\}\cup S}$ ${\displaystyle \{a^{n}bc^{n}\mid n\in {\mathcal {N}}\}}$

Las ecuaciones lingüísticas con intersección añadida corresponden análogamente a las gramáticas conjuntivas . ^{[ cita requerida ]}

Ecuaciones del lenguaje y autómatas finitos

Brzozowski y Leiss ^[2] estudiaron ecuaciones de lenguaje izquierdo donde cada concatenación es con un lenguaje constante singleton en el lado izquierdo, por ejemplo con variable , pero no ni . Cada ecuación es de la forma con una variable en el lado derecho. Cada autómata finito no determinista tiene dicha ecuación correspondiente usando concatenación izquierda y unión, vea la Figura 1. Si se permite la operación de intersección, las ecuaciones corresponden a autómatas finitos alternantes . ${\displaystyle \{a\}\cdot X}$ ${\displaystyle X}$ ${\displaystyle X\cdot Y}$ ${\displaystyle X\cdot \{a\}}$ ${\displaystyle X_{i}=F(X_{1},...,X_{k})}$

Fig. 1: Un autómata finito con sistema de ecuaciones asociado , donde es la palabra vacía. ^{[2] : 21} ${\displaystyle S_{1}=1\cdot S_{1}\cup 0\cdot S_{2}\cup \{\epsilon \}}$ ${\displaystyle S_{2}=1\cdot S_{2}\cup 0\cdot S_{1}}$ ${\displaystyle \epsilon }$

Baader y Narendran ^[3] estudiaron ecuaciones usando concatenación izquierda y unión y demostraron que su problema de satisfacibilidad es EXPTIME-completo . ${\displaystyle F(X_{1},\ldots ,X_{k})=G(X_{1},\ldots ,X_{k})}$

El problema de Conway

Conway ^[4] propuso el siguiente problema: dado un lenguaje finito constante , ¿la solución máxima de la ecuación es siempre regular? Este problema fue estudiado por Karhumäki y Petre ^{[5] [6], quienes dieron una respuesta afirmativa en un caso especial. Kunc [7]} dio una respuesta fuertemente negativa al problema de Conway, quien construyó un lenguaje finito tal que la solución máxima de esta ecuación no es recursivamente enumerable. ${\displaystyle L}$ ${\displaystyle LX=XL}$ ${\displaystyle L}$

Kunc ^[8] también demostró que la mayor solución de la desigualdad es siempre regular. ${\displaystyle LX\subseteq XL}$

Ecuaciones del lenguaje con operaciones booleanas

Las ecuaciones de lenguaje con concatenación y operaciones booleanas fueron estudiadas por primera vez por Parikh , Chandra , Halpern y Meyer ^[9], quienes demostraron que el problema de satisfacibilidad para una ecuación dada es indecidible y que si un sistema de ecuaciones de lenguaje tiene una solución única, entonces esa solución es recursiva. Más tarde, Okhotin ^[10] demostró que el problema de insatisfacibilidad es RE-completo y que cada lenguaje recursivo es una solución única de alguna ecuación.

Ecuaciones del lenguaje sobre un alfabeto unario

Para un alfabeto de una sola letra, Leiss ^[11] descubrió la primera ecuación de lenguaje con una solución no regular, utilizando operaciones de complementación y concatenación. Más tarde, Jeż ^[12] demostró que los lenguajes unarios no regulares pueden definirse mediante ecuaciones de lenguaje con unión, intersección y concatenación, equivalentes a gramáticas conjuntivas . Mediante este método, Jeż y Okhotin ^[13] demostraron que cada lenguaje unario recursivo es una solución única de alguna ecuación.

Véase también

• Gramática booleana
• La regla de Arden
• Establecer restricción

Referencias

1. Ginsburg, Seymour; Rice, H. Gordon (1962). "Dos familias de lenguajes relacionados con ALGOL". Revista de la ACM . 9 (3): 350–371. doi : 10.1145/321127.321132 . ISSN  0004-5411. S2CID  16718187.
2. Brzozowski, JA; Leiss, E. (1980). "Sobre ecuaciones para lenguajes regulares, autómatas finitos y redes secuenciales". Ciencias de la Computación Teórica . 10 (1): 19–35. doi : 10.1016/0304-3975(80)90069-9 . ISSN  0304-3975.
3. Baader, Franz; Narendran, Paliath (2001). "Unificación de términos conceptuales en lógicas descriptivas". Journal of Symbolic Computation . 31 (3): 277–305. doi : 10.1006/jsco.2000.0426 . ISSN  0747-7171.
4. Conway, John Horton (1971). Álgebra regular y máquinas finitas . Chapman y Hall. ISBN 978-0-486-48583-6.
5. Karhumäki, Juhani; Petre, Ion (2002). "El problema de Conway para conjuntos de tres palabras". Ciencias Informáticas Teóricas . 289 (1): 705–725. doi : 10.1016/S0304-3975(01)00389-9 . ISSN  0304-3975.
6. Karhumäki, Juhani; Petre, Ion (2002). El enfoque del punto de ramificación para el problema de Conway . Apuntes de clase en informática. Vol. 2300. págs. 69–76. doi :10.1007/3-540-45711-9_5. ISBN 978-3-540-43190-9. ISSN  0302-9743.
7. Kunc, Michal (2007). "El poder de conmutar con conjuntos finitos de palabras". Teoría de sistemas informáticos . 40 (4): 521–551. doi :10.1007/s00224-006-1321-z. ISSN  1432-4350. S2CID  13406797.
8. Kunc, Michal (2005). "Soluciones regulares de desigualdades del lenguaje y cuasiórdenes". Ciencias Informáticas Teóricas . 348 (2–3): 277–293. doi : 10.1016/j.tcs.2005.09.018 . ISSN  0304-3975.
9. Parikh, Rohit; Chandra, Ashok; Halpern, Joe; Meyer, Albert (1985). "Ecuaciones entre términos regulares y una aplicación a la lógica de procesos". Revista SIAM de Computación . 14 (4): 935–942. doi :10.1137/0214066. ISSN  0097-5397.
10. Okhotin, Alexander (2010). "Problemas de decisión para ecuaciones de lenguaje". Revista de Ciencias de la Computación y de Sistemas . 76 (3–4): 251–266. doi : 10.1016/j.jcss.2009.08.002 . ISSN  0022-0000.
11. Leiss, EL (1994). "Complementación sin restricciones en ecuaciones de lenguaje sobre un alfabeto de una letra". Ciencias Informáticas Teóricas . 132 (1–2): 71–84. doi : 10.1016/0304-3975(94)90227-5 . ISSN  0304-3975.
12. Jeż, Artur (2008). "Las gramáticas conjuntivas generan lenguajes unarios no regulares". Revista Internacional de Fundamentos de la Ciencia de la Computación . 19 (3): 597–615. doi :10.1142/S012905410800584X. ISSN  0129-0541.
13. Jeż, Artur; Okhotin, Alexander (2014). "Completitud computacional de ecuaciones sobre conjuntos de números naturales". Información y computación . 237 : 56–94. CiteSeerX 10.1.1.395.2250 . doi :10.1016/j.ic.2014.05.001. ISSN  0890-5401. 

Enlaces externos

• Taller sobre teoría y aplicaciones de ecuaciones del lenguaje (TALE 2007)