L1

universityin-classsubject-1202

2023-03-06

Fondamenti di Informatica

Linguaggi Formali

Applicazioni d’esempio:

• Ricerca di una parola in un testo (usa proprietà dei linguaggi formali)
• Il DNA
• I compilatori

Alfabeto: insieme finito di simboli (si indica con ). es.
Linguaggio formale (vedi sotto definizione formale): insieme di parole di lunghezza finita costruite a partire da un determinato alfabeto.
Stringa Parola: sequenza (di lunghezza finita) di simboli dell’alfabeto.

Quante sono le combinazioni di parole (lunghezza finita) rispetto a un alfabeto (finito)?: sono infinite.
Basti pensare a quanti numeri esistono. Numeri finiti con numero di cifre finito.

Stringhe particolari:

• Stringa vuota: stringa che non contiene nessun simbolo (si indica con , oppure )
  • Es.

Nota: per notazione vengono usate per indicare parole e per indicare simboli.

Dato un alfabeto , l’insieme delle stringhe costruite su si indica con , ed è così definito:

2. Se e , allora

Esercizio: dato , dimostriamo che

1. e .
2. e .
3. e .

• Quindi . Si può dimostrare anche al contrario andando ricorsivamente

Sia alfabeto e , la concatenazione di e si indica con ed è la stringa data da .

• La concatenazione è chiusa rispetto a .
• è l’elemento neutro della concatenazione.
• Vale la proprietà associativa.
• Possiamo quindi dire che è un monoide (rispetto al gruppo il monoide non ha l’inverso) sintattico.

Lunghezza di una parola: dato alfabeto, la lunghezza di una parola si indica con ed è così definita:

1. Se allora .
2. Se dove e allora .

Dato e , se allora

Definizione di Linguaggio Formale: dato un alfabeto , un linguaggio formale su è un qualsiasi sottoinsieme di .
Linguaggi particolari:

• Linguaggio vuoto (): è un insieme vuoto, non un insieme che contiene .

Concatenazione di linguaggi
,
da finire