Kurodin normalni oblik

U računarstvu, formalna gramatika je u Kurodinom normalnom obliku ako i samo ako ima sve produkcije oblika:
AB → CD ili
A → BC ili
A → B ili
A → α
pri čemu su A, B, C i D nezavršni znakovi i α je završni znak.

Svaka gramatika u Kurodinom normalnom obliku generiše kontekstno zavisni jezik i obrnuto, svaki kontekstno ovisni jezik koji ne generiše prazni niz se može izgenerisati gramatikom u Kurodinom normalnom oblku.

 Reference 
 S.-Y. Kuroda, Classes of languages and linear-bounded automata, Information and Control 7(2): 207–223, juni 1964.

 Literatura 

 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.  (Révész' trick)


 Također pogledajte 
 Chomskyjev normalni oblik
 Greibachov normalni oblik

Kategorija:Formalni jezici