Kurodin normalni oblik

Sa Wikipedije, slobodne enciklopedije
Idi na: navigacija, traži
Question book-new.svg 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 | uredi izvor]

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

Također pogledajte[uredi | uredi izvor]