Indietro

ⓘ Forma normale di Kuroda




                                     

ⓘ Forma normale di Kuroda

In informatica, una grammatica formale è espressa in forma normale di Kuroda se tutte le sue produzioni sono della forma:

AB → CD oppure A → BC oppure A → B oppure A → α

dove A, B, C e D sono simboli non terminali α è un simbolo terminale.

Ogni grammatica in forma normale di Kuroda genera un Linguaggio sensibile al contesto, e, viceversa, ogni linguaggio sensibile al contesto che non produce la stringa vuota può essere generata da una grammatica in forma normale di Kuroda.