Hispanopedia Wiki
Articulo de referencia

Ecuación del lenguaje

Las ecuaciones de lenguaje son enunciados matemáticos que se asemejan a ecuaciones numéricas , pero las variables toman valores de lenguajes formales en lugar de números. En lug...

Hispanopedia WikiContenido en espanolLectura gratuita

Las ecuaciones de lenguaje son enunciados matemáticos que se asemejan a ecuaciones numéricas , pero las variables toman valores de lenguajes formales en lugar de números. En lugar de operaciones aritméticas, como en las ecuaciones numéricas, las variables se combinan mediante operaciones de lenguaje. Entre las operaciones más comunes sobre dos lenguajes A y B se encuentran la unión de conjuntos A ∪ B , la intersección de conjuntos A ∩ B y la concatenación A ⋅ B. Finalmente, como 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 lingüísticas 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 contextoGRAMO=(V,Σ,R,S){\displaystyle G=(V,\Sigma,R,S)}, se asocia un sistema de ecuaciones en variablesV{\displaystyle V}Cada variableincógnita∈V{\displaystyle X\in V}es un idioma desconocido sobreΣ{\displaystyle \Sigma }y se define mediante la ecuaciónincógnita=α1∪…∪αmetro{\displaystyle X=\alpha _{1}\cup \ldots \cup \alpha _{m}}dóndeincógnita→α1{\displaystyle X\to \alpha _{1}}, ...,incógnita→αmetro{\displaystyle X\to \alpha _{m}}son todas producciones paraincógnita{\displaystyle X}Ginsburg y Rice utilizaron un argumento de iteración de punto fijo para demostrar que siempre existe una solución y probaron que la asignaciónincógnita=LGRAMO(incógnita){\displaystyle X=L_{G}(X)}es la solución mínima para este sistema, es decir, cualquier otra solución debe ser un subconjunto de esta.

Por ejemplo, la gramática S→aSdo∣b∣S{\displaystyle S\to aSc\mid b\mid S} corresponde al sistema de ecuaciones S=({a}⋅S⋅{do})∪{b}∪S{\displaystyle S=(\{a\}\cdot S\cdot \{c\})\cup \{b\}\cup S} que tiene como solución cada superconjunto de{anortebdonorte∣norte∈norte}{\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 .

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 unitario a la izquierda, por ejemplo{a}⋅incógnita{\displaystyle \{a\}\cdot X}con variableincógnita{\displaystyle X}pero noincógnita⋅Y{\displaystyle X\cdot Y}niincógnita⋅{a}{\displaystyle X\cdot \{a\}}Cada ecuación tiene la formaincógnitai=F(incógnita1,...,incógnitak){\displaystyle X_{i}=F(X_{1},...,X_{k})}con una variable en el lado derecho. Todo autómata finito no determinista tiene una ecuación correspondiente utilizando concatenación izquierda y unión, véase la Fig. 1. Si se permite la operación de intersección, las ecuaciones corresponden a autómatas finitos alternados .

Figura 1: Un autómata finito con su sistema de ecuaciones asociado.S1=1⋅S1∪0⋅S2∪{ϵ}{\displaystyle S_{1}=1\cdot S_{1}\cup 0\cdot S_{2}\cup \{\epsilon \}},S2=1⋅S2∪0⋅S1{\displaystyle S_{2}=1\cdot S_{2}\cup 0\cdot S_{1}}dóndeϵ{\displaystyle \epsilon }es la palabra vacía. [ 2 ] : 21

Baader y Narendran [ 3 ] estudiaron ecuacionesF(incógnita1,…,incógnitak)=GRAMO(incógnita1,…,incógnitak){\displaystyle F(X_{1},\ldots ,X_{k})=G(X_{1},\ldots ,X_{k})}utilizando concatenación izquierda y unión, demostraron que su problema de satisfacibilidad es EXPTIME-completo .

El problema de Conway

Conway [ 4 ] propuso el siguiente problema: dado un lenguaje finito constanteL{\displaystyle L}es la mayor solución de la ecuaciónLincógnita=incógnitaL{\displaystyle LX=XL}¿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, al construir un lenguaje finito.L{\displaystyle L}de tal manera que la mayor solución de esta ecuación no sea recursivamente enumerable.

Kunc [ 8 ] también demostró que la mejor solución de la desigualdadLincógnita⊆incógnitaL{\displaystyle LX\subseteq XL}Siempre es regular.

Ecuaciones de 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. Posteriormente, Okhotin [ 10 ] demostró que el problema de insatisfacibilidad es RE-completo y que todo lenguaje recursivo es una solución única de alguna ecuación.

Ecuaciones lingüísticas 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. Posteriormente, 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 todo lenguaje unario recursivo es una solución única de alguna ecuación.

Véase también

Referencias

  1. ↑ Ginsburg, Seymour; Rice, H. Gordon (1962). "Dos familias de lenguajes relacionados con ALGOL" . Journal of the 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" . Informática 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 de descripción" . 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 and Hall. ISBN 978-0-486-48583-6.
  5. ↑ Karhumäki, Juhani; Petre, Ion (2002). "El problema de Conway para conjuntos de tres palabras" . Theoretical Computer Science . 289 (1): 705– 725. doi : 10.1016/S0304-3975(01)00389-9 . ISSN 0304-3975 . 
  6. ↑ Karhumäki, Juhani; Petre, Ion (2002). El enfoque de puntos de ramificación al problema de Conway . Lecture Notes in Computer Science. Vol. 2300. pp. 69–76 . doi : 10.1007/3-540-45711-9_5 . ISBN   978-3-540-43190-9ISSN 0302-9743​​ 
  7. ↑ Kunc, Michal (2007). "El poder de la conmutación con conjuntos finitos de palabras". Theory of Computing Systems . 40 (4): 521– 551. doi : 10.1007/s00224-006-1321-z . ISSN 1432-4350 . S2CID 13406797 .  
  8. ↑ Kunc, Michal (2005). "Soluciones regulares de desigualdades de lenguaje y cuasiórdenes bien definidos" . Theoretical Computer Science . 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". SIAM Journal on Computing . 14 (4): 935– 942. doi : 10.1137/0214066 . ISSN 0097-5397 . 
  10. ↑ Okhotin, Alexander (2010). "Problemas de decisión para ecuaciones de lenguaje" . Journal of Computer and System Sciences . 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" . Theoretical Computer Science . 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 Informática . 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". Information and Computation . 237 : 56–94 . CiteSeerX 10.1.1.395.2250 . doi : 10.1016/j.ic.2014.05.001 . ISSN 0890-5401 .  
  • Taller sobre Teoría y Aplicaciones de las Ecuaciones del Lenguaje (TALE 2007)