Usuario:LSam650/Taller1

En la teoría de lenguajes formales, una gramática monótona está en forma normal de Kuroda (FNK) si todas sus reglas de producción son de la forma:

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. Algunas fuentes omiten la producción A → B.

Lleva el nombre de Sige-Yuki Kuroda, quien lo llamó gramática lineal limitada (GLL), una terminología que también fue utilizada por otros autores en adelante.

Cada gramática en la forma normal de Kuroda es monótona y genera un lenguaje sensible al contexto. Por otro lado, cada gramática monótona que no genera la cadena vacía es posible convertirla a la forma normal de Kuroda.

Otra técnica atribuida a György Révész

transforma una gramática en FNK en una gramática sensible al contexto: AB → CD

se puede reemplazar por cuatro reglas sensibles al contexto AB → AZ, AZ → WZ, WZ → WD y WD → CD . Esto prueba que toda gramática monotóna genera un lenguaje sensible al contexto.

Existe una forma normal similar para gramáticas no restringidas, algunos autores lo llaman "forma normal de Kuroda":

AB → CD o

A → BC o

A → a o

A → ε

ε es la cadena vacía. Una gramática no restringida es débil comparado con una que usa solo producciones de esta forma.

Si se elimina la regla AB → CD se obtienen gramáticas libres de contexto en la Forma Normal de Chomsky (FNCH) . La forma normal de Penttonen para gramáticas no restringidas es un caso especial donde la primera regla anterior es AB → AD.

De igual forma, para las gramáticas sensibles al contexto, la forma unilateral (forma normal de Penttonen) es:

AB → AD o

A → BC o

A → a

Para cada gramática sensible al contexto, existe una forma normal unilateral equivalente pero débil.

Véase también

• Backus–Naur form
• Chomsky normal form
• Greibach normal form

Otras lecturas

• Sige-Yuki Kuroda (June 1964). «Classes of languages and linear-bounded automata». Information and Control 7 (2): 207–223. doi:10.1016/S0019-9958(64)90120-2. 
• G. Révész, "Comment on the paper 'Error detection in formal languages,'" Journal of Computer and System Sciences, vol. 8, no. 2, pp. 238–242, Apr. 1974. doi 10.1016/S0022-0000(74)80057-7 (Révész' trick)
• Penttonen, Martti (Aug 1974). «One-sided and two-sided context in formal grammars». Information and Control 25 (4): 371-392. doi:10.1016/S0019-9958(74)91049-3.