Postać normalna Kurody

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Gramatyka formalna jest w postaci normalnej Kurody, jeśli zawiera tylko produkcje postaci: , , , , gdzie A,B i C to symbole nieterminalne, a - symbol terminalny.

Każda gramatyka w postaci normalnej Kurody generuje język kontekstowy, jak również dla każdej gramatyki kontekstowej nie generującej słowa pustego istnieje równoważna jej gramatyka w postaci normalnej Kurody.

Bibliografia[edytuj]

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