Hispanopedia Wiki
Articulo de referencia

Kuroda en su forma normal

En la teoría del lenguaje formal , una gramática no contractiva está en forma normal de Kuroda si todas las reglas de producción son de la forma: [ 1 ] AB → CD o A → BC o A → B ...

Hispanopedia WikiContenido en espanolLectura gratuita

En la teoría del lenguaje formal , una gramática no contractiva está en forma normal de Kuroda si todas las reglas de producción son de la forma: [ 1 ]

AB → CD o
A → BC o
A → B o
A → a

donde A, B, C y D son símbolos no terminales y a es un símbolo terminal . [ 1 ] Algunas fuentes omiten el patrón A → B. [ 2 ]

Recibe su nombre de Sige-Yuki Kuroda , quien originalmente la denominó gramática lineal acotada , una terminología que posteriormente también utilizaron otros autores. [ 3 ]

Toda gramática en forma normal de Kuroda es no contractiva y, por lo tanto, genera un lenguaje sensible al contexto . A la inversa, toda gramática no contractiva que no genere la cadena vacía puede convertirse a la forma normal de Kuroda. [ 2 ]

Una técnica sencilla atribuida a György Révész transforma una gramática en forma normal de Kuroda en una gramática sensible al contexto : AB → CD se reemplaza por cuatro reglas sensibles al contexto AB → AZ , AZ → WZ , WZ → WD y WD → CD . Esto demuestra que toda gramática no contractiva genera un lenguaje sensible al contexto. [ 1 ]

También existe una forma normal similar para las gramáticas no restringidas , que al menos algunos autores también llaman "forma normal de Kuroda": [ 4 ]

AB → CD o
A → BC o
A → a o
A → ε

donde ε es la cadena vacía. Toda gramática no restringida es débilmente equivalente a una que utiliza solo producciones de esta forma. [ 2 ]

Si se elimina la regla AB → CD de lo anterior, se obtienen gramáticas libres de contexto en la forma normal de Chomsky . [ 5 ] La forma normal de Penttonen (para gramáticas no restringidas) es un caso especial donde la primera regla anterior es AB → AD . [ 4 ] De manera similar, para gramáticas sensibles al contexto, la forma normal de Penttonen, también llamada forma normal unilateral (siguiendo la propia terminología de Penttonen) es: [ 1 ] [ 2 ]

AB → AD o
A → BC o
A → a

Para cada gramática sensible al contexto, existe una forma normal unilateral débilmente equivalente. [ 2 ]

Véase también

Referencias

  1. 1 2 3 4 Masami Ito; Yuji Kobayashi; Kunitaka Shoji (2010). Autómatas, lenguajes formales y sistemas algebraicos: actas de AFLAS 2008, Kyoto, Japón, 20-22 de septiembre de 2008 . Científico mundial. pag.  182.ISBN​ 978-981-4317-60-3.
  2. 1 2 3 4 5 Mateescu, Alexandru; Salomaa, Arto (1997). "Capítulo 4: Aspectos de la teoría del lenguaje clásico". En Rozenberg, Grzegorz; Salomaa, Arto (eds.). Manual de lenguajes formales. Tomo I: Palabra, lengua, gramática . Springer-Verlag. pag. 190.ISBN​  978-3-540-61486-9.
  3. ↑ Willem JM Levelt (2008). Introducción a la teoría de los lenguajes formales y los autómatas . John Benjamins Publishing. págs. 126–127 . ISBN  978-90-272-3250-2.
  4. 1 2 Alexander Meduna (2000). Autómatas y lenguajes: teoría y aplicaciones . Springer Science & Business Media. pág. 722. ISBN  978-1-85233-074-3.
  5. ↑ Alexander Meduna (2000). Autómatas y lenguajes: teoría y aplicaciones . Springer Science & Business Media. pág. 728. ISBN  978-1-85233-074-3.

Lecturas adicionales

  • Sige-Yuki Kuroda (junio de 1964). "Clases de lenguajes y autómatas linealmente acotados" . Information and Control . 7 (2): 207– 223. doi : 10.1016/S0019-9958(64)90120-2 .
  • G. Révész, "Comentario sobre el artículo 'Detección de errores en lenguajes formales'", Journal of Computer and System Sciences, vol. 8, núm. 2, págs.  238–242, abril de 1974. doi : 10.1016/S0022-0000(74)80057-7 (el truco de Révész)
  • Penttonen, Martti (agosto de 1974). "Contexto unilateral y bilateral en gramáticas formales" . Information and Control . 25 (4): 371– 392. doi : 10.1016/S0019-9958(74)91049-3 .