Postać normalna Kurody

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania

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 | edytuj kod]

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