Kurodin normalni oblik
Sa Wikipedije, slobodne enciklopedije
 |
Ovaj članak ili neka od njegovih sekcija nije dovoljno potkrijepljena izvorima (literatura, web stranice ili drugi izvori). Sporne rečenice i navodi bi mogli, ukoliko se pravilno ne označe validnim izvorima, biti obrisani i uklonjeni. Pomozite Wikipediji tako što ćete navesti validne izvore putem referenci, te nakon toga možete ukloniti ovaj šablon. |
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]
- S.-Y. Kuroda, Classes of languages and linear-bounded automata, Information and Control 7(2): 207–223, juni 1964.
