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.
Fonti modifica
- S.-Y. Kuroda, Classes of languages and linear-bounded automata, Information and Control 7(2): 207–223, June 1964.
