En la teoría del lenguaje formal , una gramática sensible al contexto está en la forma normal de Kuroda si todas las reglas de producción tienen 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]
Lleva el nombre de Sige-Yuki Kuroda , quien originalmente la llamó una gramática limitada lineal, una terminología que también fue utilizada por algunos otros autores a partir de entonces. [3]
Cada gramática en la forma normal de Kuroda no se contrae y, por lo tanto, genera un lenguaje sensible al contexto . A la inversa, cada lenguaje sensible al contexto que no genere la cadena vacía puede ser generado por una gramática en la forma normal de Kuroda. [2]
Una técnica sencilla atribuida a György Révész transforma una gramática en la forma de Kuroda al CSG de Chomsky: AB → CD se reemplaza por cuatro reglas sensibles al contexto AB → AZ , AZ → WZ , WZ → WD y WD → CD . Esta técnica también demuestra que toda gramática no contractual es 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. Cada gramática no restringida es [débilmente] [ se necesita más explicación ] equivalente a una que usa solo producciones de esta forma. [2]
Si se elimina la regla AB → CD de lo anterior, se obtienen lenguajes libres de contexto. [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 las 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 equivalente [débilmente] [ se necesita más explicación ] . [2]
Ver también
Referencias
- ^ a b c d Masami Ito; Yūji Kobayashi; Kunitaka Shoji (2010). Autómatas, lenguajes formales y sistemas algebraicos: Actas de AFLAS 2008, Kyoto, Japón, 20-22 de septiembre de 2008 . World Scientific. pag. 182. ISBN 978-981-4317-60-3.
- ^ a b c d e 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. Volumen I: Palabra, lenguaje, gramática . Springer-Verlag. pag. 190. ISBN 978-3-540-61486-9.
- ^ Willem JM Levelt (2008). Introducción a la teoría de lenguajes formales y autómatas . Editorial John Benjamins. págs. 126-127. ISBN 978-90-272-3250-2.
- ^ a b Alexander Meduna (2000). Autómatas y lenguajes: teoría y aplicaciones . Springer Science & Business Media. pag. 722. ISBN 978-1-85233-074-3.
- ^ Alexander Meduna (2000). Autómatas y lenguajes: teoría y aplicaciones . Springer Science & Business Media. pag. 728. ISBN 978-1-85233-074-3.
Otras lecturas
- Sige-Yuki Kuroda (junio de 1964). "Clases de lenguajes y autómatas acotados linealmente" . Información y 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'", Revista de Ciencias de la Computación y Sistemas, vol. 8, no. 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" . Información y control . 25 (4): 371–392. doi : 10.1016 / S0019-9958 (74) 91049-3 .