Kuroda-Normalform
Die Kuroda-Normalform ist ein Begriff der Theoretischen Informatik, der im Zusammenhang mit kontextsensitiven Sprachen von Interesse ist. Sie ist nach dem Linguisten Sige-Yuki Kuroda benannt und beschreibt eine Normalform der monotonen Grammatiken, also eine Teilmenge der monotonen Grammatiken, die gegenüber der Menge aller monotonen Grammatiken nichts an Ausdrucksstärke einbüßt. Die Bedeutung der Kuroda-Normalform liegt in der sehr einfachen Struktur der Produktionen. Weil monotone Grammatiken und kontextsensitive Grammatiken gelegentlich nicht unterschieden werden, wird die Kuroda-Normalform auch als Normalform der kontextsensitiven Grammatiken bezeichnet.
Die Kuroda-Normalform ist eine Verallgemeinerung der Chomsky-Normalform, die eine Normalform für kontextfreie Grammatiken ist.
Kuroda-Normalform
Die Kuroda-Normalform ist ein Begriff der Theoretischen Informatik, der im Zusammenhang mit kontextsensitiven Sprachen von Interesse ist. Sie ist nach dem Linguisten Sige-Yuki Kuroda benannt und beschreibt eine Normalform der monotonen Grammatiken, also eine Teilmenge der monotonen Grammatiken, die gegenüber der Menge aller monotonen Grammatiken nichts an Ausdrucksstärke einbüßt. Die Bedeutung der Kuroda-Normalform liegt in der sehr einfachen Struktur der Produktionen. Weil monotone Grammatiken und kontextsensitive Grammatiken gelegentlich nicht unterschieden werden, wird die Kuroda-Normalform auch als Normalform der kontextsensitiven Grammatiken bezeichnet.
Die Kuroda-Normalform ist eine Verallgemeinerung der Chomsky-Normalform, die eine Normalform für kontextfreie Grammatiken ist.