Fondamenti di informatica - Laurea triennale Informatica/Linguaggi e grammatiche

Il linguaggio formale è diverso dai linguaggi naturali. I linguaggi naturali, come l’italiano o l’inglese, hanno regole complesse e spesso difficili da descrivere completamente. I linguaggi formali, invece, sono definiti in modo preciso tramite regole matematiche e sono molto importanti in informatica, soprattutto per descrivere linguaggi di programmazione e sistemi di calcolo.

Un linguaggio formale su un alfabeto finito è un insieme di stringhe costruite usando i simboli di quell’alfabeto. Per esempio, se l’alfabeto è formato da {0, 1}, allora un linguaggio può essere l’insieme di tutte le stringhe che contengono un numero dispari di 1.

Le grammatiche

Le grammatiche sono sistemi di regole usati per generare linguaggi (ovvero le stringhe che li compongono). Una grammatica è composta da:

• un insieme finito di simboli non terminali;
• un insieme finito di simboli terminali;
• un insieme di produzioni, cioè regole di riscrittura;
• un simbolo iniziale.

I simboli terminali sono quelli che compaiono nelle stringhe finali del linguaggio, mentre i simboli non terminali servono come elementi intermedi durante la derivazione.

Una stringa viene generata partendo dal simbolo iniziale e applicando più volte le produzioni fino a ottenere una stringa composta solo da simboli terminali. L’insieme di tutte le stringhe ottenibili in questo modo è detto linguaggio generato dalla grammatica.

Una stringa è direttamente derivabile da un’altra se si ottiene applicando una sola produzione. È invece derivabile se si ottiene tramite una sequenza di più passaggi. Per convenzione, ogni stringa è derivabile da sé stessa.

La Backus Normal Form, detta anche Backus–Naur Form o BNF è una notazione usata per scrivere le produzioni grammaticali in modo più leggibile. In BNF, i simboli non terminali sono spesso racchiusi tra parentesi angolari, come <integer> o <digit>, e il simbolo | significa “oppure”. Questa notazione è molto usata per descrivere la sintassi dei linguaggi di programmazione come Java e C++.

Un esempio importante è la grammatica degli interi, dove un numero intero è definito come una stringa formata da un eventuale segno + o -, seguito da una sequenza di cifre da 0 a 9.

Classificazioni delle grammatiche

• Grammatiche context-sensitive, o di tipo 1:

Le produzioni permettono di sostituire un simbolo non terminale tenendo conto del contesto in cui si trova.

• Grammatiche context-free, o di tipo 2:

Le produzioni permettono di sostituire un singolo simbolo non terminale indipendentemente dal contesto.

• Grammatiche regolari, o di tipo 3:

Hanno regole molto semplici: un simbolo non terminale può essere sostituito da un simbolo terminale, da un terminale seguito da un non terminale, oppure dalla stringa nulla.

Ogni grammatica regolare è anche context-free, alcune grammatiche context-free possono essere considerate context-sensitive se non usano produzioni che generano la stringa nulla.

I linguaggi

Un linguaggio è un insieme di stringhe generato da una specifica grammatica.

Un linguaggio L si dice:

• sensibile al contesto se esiste una grammatica sensibile al contesto che genera L;
• libero dal contesto se esiste una grammatica libera dal contesto che genera L;
• regolare se esiste una grammatica regolare che genera L.

In simboli, se una grammatica G genera il linguaggio L, si scrive:

L=L(G)

cioè L è l’insieme di tutte le stringhe che possono essere derivate dalla grammatica G.

Gerarchia dei linguaggi

Esiste una gerarchia tra le classi di linguaggi:

linguaggi regolari⊂linguaggi context-free⊂linguaggi context-sensitive

Queste inclusioni sono proprie, cioè ogni classe è contenuta nella successiva, ma non coincide con essa.

In altre parole:

• ogni linguaggio regolare è anche context-free;
• ogni linguaggio context-free, purché non contenga la stringa nulla, è anche context-sensitive;
• esistono linguaggi context-free che non sono regolari;
• esistono linguaggi context-sensitive che non sono context-free;
• esistono anche linguaggi che non sono context-sensitive.

Esempio di linguaggio context-sensitive ma non context-free

Un esempio importante è il linguaggio:

L={anbncn∣n≥1}

Questo linguaggio contiene stringhe formate da:

1. un certo numero di a,
2. lo stesso numero di b,
3. lo stesso numero di c.

Per esempio:

abc,aabbcc,aaabbbccc

Questo linguaggio è context-sensitive, ma non è context-free.

Il motivo intuitivo è che una grammatica libera dal contesto riesce a controllare bene una corrispondenza tra due quantità, come anbn, ma non riesce a imporre contemporaneamente l’uguaglianza tra tre gruppi a, b, c.

Esempio di linguaggio context-free ma non regolare

Un altro esempio è il linguaggio:

L={0n1n∣n≥0}

Questo linguaggio contiene stringhe formate da un certo numero di 0, seguito dallo stesso numero di 1.

Per esempio:

λ,01,0011,000111

Questo linguaggio è context-free, perché può essere generato da una grammatica con produzioni del tipo:

S→0S1

e poi eventualmente:

S→λ

Le derivazioni hanno la forma:

S⇒0S1⇒00S11⇒⋯⇒0n1n

Tuttavia, questo linguaggio non è regolare, perché un linguaggio regolare non ha memoria sufficiente per contare quanti 0 sono stati letti e verificare che ci sia lo stesso numero di 1.

---

Linguaggi regolari

Un linguaggio generato da una grammatica regolare è, per definizione, un linguaggio regolare.

Un esempio riguarda il linguaggio delle stringhe che rappresentano interi. Inizialmente può essere data una grammatica context-free ma non regolare; tuttavia, modificando opportunamente le produzioni, si ottiene una grammatica regolare che genera lo stesso linguaggio.

Questo dimostra che non è importante soltanto la forma di una singola grammatica: uno stesso linguaggio può essere generato da grammatiche diverse.

---

Grammatiche equivalenti

Due grammatiche G1​ e G2​ si dicono equivalenti se generano lo stesso linguaggio:

L(G1​)=L(G2​)

Quindi due grammatiche possono avere produzioni diverse, simboli diversi o strutture diverse, ma se producono esattamente lo stesso insieme di stringhe, sono considerate equivalenti.

Per esempio, una grammatica context-free e una grammatica regolare possono essere equivalenti se entrambe generano lo stesso linguaggio.

---

Relazione di equivalenza tra grammatiche

Il testo osserva infine che la relazione “essere equivalente a” tra grammatiche è una relazione di equivalenza.

Questo significa che gode di tre proprietà:

1. Riflessiva: ogni grammatica è equivalente a se stessa. G∼G
2. Simmetrica: se G1​ è equivalente a G2​, allora G2​ è equivalente a G1​. G1​∼G2​⇒G2​∼G1​
3. Transitiva: se G1​ è equivalente a G2​ e G2​ è equivalente a G3​, allora G1​ è equivalente a G3​. G1​∼G2​,G2​∼G3​⇒G1​∼G3​

Di conseguenza, l’insieme delle grammatiche può essere diviso in classi di equivalenza, dove ogni classe contiene tutte le grammatiche che generano lo stesso linguaggio.