Teoria dei linguaggi formali
![Abbozzo](http://upload.wikimedia.org/wikipedia/commons/thumb/0/0e/Puzzle_stub.svg/45px-Puzzle_stub.svg.png)
Questa voce sull'argomento teorie dell'informatica è solo un abbozzo.
Contribuisci a migliorarla secondo le convenzioni di Wikipedia.
La teoria dei linguaggi formali è un ramo della matematica applicata che studia gli insiemi di stringhe, cioè i linguaggi formali, e le loro proprietà, seguendo vari approcci. Le proprietà studiate trovano applicazione in logica, informatica e linguistica.
- Approccio 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 qualche altro sistema di riscrittura.
- Approccio riconoscitivo: un linguaggio viene definito come l'insieme di tutte e sole le stringhe che vengono accettate da un automa.
- Approccio denotazionale: un linguaggio viene definito mediante espressioni simboliche compatte, come le espressioni regolari, che ne denotano (tutte e sole) le stringhe in forma concisa.
- Approccio algebrico: un linguaggio viene definito attraverso sue proprietà algebriche, in particolare proprietà riconducibili alla teoria dei semigruppi e alle algebre di Kleene.
- Approccio trasformazionale: un linguaggio viene definito come ottenuto sottoponendo a una data trasformazione un altro linguaggio, tendenzialmente più semplice.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/7/77/Computer_n_screen.svg/24px-Computer_n_screen.svg.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/a/af/Crystal128-kmplot.svg/25px-Crystal128-kmplot.svg.png)