Postać normalna Kurody

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

Gramatyka formalna jest w postaci normalnej Kurody, jeśli zawiera tylko produkcje postaci: AB \rightarrow CD, A \rightarrow BC, A \rightarrow B, A \rightarrow \alpha, gdzie A,B i C to symbole nieterminalne, a \alpha - 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.