stringtranslate.com

Forma normal de Kuroda

En la teoría del lenguaje formal , una gramática no contráctil 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
Un → un

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 en honor a Sige-Yuki Kuroda , quien originalmente la llamó gramática lineal limitada , una terminología que también fue utilizada por algunos otros autores posteriormente. [3]

Toda gramática en la forma normal de Kuroda no es contráctil y, por lo tanto, genera un lenguaje sensible al contexto . Por el contrario, toda gramática no contráctil que no genere la cadena vacía se puede convertir 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 contráctil genera un lenguaje sensible al contexto. [1]

También existe una forma normal similar para gramáticas sin restricciones , 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 sin restricciones es débilmente equivalente a una que utilice únicamente 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 sin restricciones) 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
Un → un

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

Véase también

Referencias

  1. ^ abcd Masami Ito; Yūji Kobayashi; Kunitaka Shoji (2010). Autómatas, lenguajes formales y sistemas algebraicos: Actas de AFLAS 2008, Kioto, Japón, 20-22 de septiembre de 2008. World Scientific. pág. 182. ISBN 978-981-4317-60-3.
  2. ^ abcde 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 lenguajes formales y autómatas. John Benjamins Publishing. pp. 126-127. ISBN 978-90-272-3250-2.
  4. ^ de 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.

Lectura adicional