Linguaggi
‘Ma cos”è un linguaggio? Un oggetto matematico formato da:
- alfabeto (segni/simboli)
- stringhe formate dagli elementi del alfabeto (sequenze ordinate)
Linguaggi come estrema astrazione. Ad esempio le stringhe possono essere formate non da lettere, ma simboli che rappresentano ad esempio le azioni che fa un programma. Altro esempio è scrivere un problema che ci affligge in un determinato linguaggio e cercare le soluzioni-stringhe appartenenti al linguaggio delle soluzioni corrette. Dobbiamo poi definire la concatenazione di stringhe, la quale nella sua versione generalizzata si identifica come concatenazione di linguaggi.
Stella di Kleene : (x)* è l’insieme di tutte le stringhe ottenibili concatenando x a sè stessa, arbitrariamente (anche 0 volte).