Postać normalna Kurody

Gramatyka formalna jest w postaci normalnej Kurody, jeśli zawiera tylko produkcje postaci: $AB\to CD,$ $A\to BC,$ $A\to B,$ $A\to \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

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