Teoria dei linguaggi formali
La Teoria dei Linguaggi Formali studia i linguaggi formali e le loro proprietà utilizzando vari approcci:
- generativo: un linguaggio viene definito come l'insieme di tutte e sole le stringhe che vengono prodotte da una grammatica generativa, da un sistema di Lyndenmayer o da qulche altro sistema di riscrittura;
- riconoscitivo: un linguaggio viene definito come l'insieme di tutte e sole le stringhe che vengono accettate da un automa;
- denotazionale: un linguaggio viene definito mediante espressioni simboliche compatte come espressioni regolari che ne denotano (tutte e sole) le stringhe in forma compatta;
- algebrico: un linguaggio viene definito attraverso sue proprietà algebriche, in particolare proprietà riconducibili alla teoria dei semigruppi;
- trasformazionale: un linguaggio viene definito come ottenuto sottoponendo a una data trasformazione un altro linguaggio, tendenzialmente più semplice.