Kurodin normalni oblik

S Wikipedije, slobodne enciklopedije
Idi na navigaciju Idi na pretragu

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[uredi | uredi izvor]

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

Literatura[uredi | uredi izvor]

  • Sige-Yuki Kuroda (juni 1964). "Classes of languages and linear-bounded automata" (PDF). 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 (august 1974). "One-sided and two-sided context in formal grammars" (PDF). Information and Control. 25 (4): 371–392. doi:10.1016/S0019-9958(74)91049-3.

Također pogledajte[uredi | uredi izvor]