Forma normale di Kuroda

Da Wikipedia, l'enciclopedia libera.

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 | modifica sorgente]

  • S.-Y. Kuroda, Classes of languages and linear-bounded automata, Information and Control 7(2): 207–223, June 1964.
informatica Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica