Informatica di base

SUPPONIAMO CHE:

Supponiamo che sia possibile sviluppare l’algoritmo “termina?”, che prende in input

un certo algoritmo, e restituisce:

● “Vero” nel caso in cui l’algoritmo, specificato come input, termina.

● “Falso” nel caso in cui l’algoritmo, specificato come input, non termina.

Ovviamente si tratta di un algoritmo ipotetico: stiamo supponendo che possiamo

svilupparlo in qualche modo, senza mostrare come farlo davvero

Ora usiamo l’algoritmo “termina?” per sviluppare un nuovo algoritmo (diagramma di

flusso in figura). Questo nuovo algoritmo, restituisce:

● 0 se l’algoritmo in input non termina

● “Non termina” in caso contrario

La domanda è: Cosa succede se cerchiamo di eseguire l’algoritmo descritto in figura

usando se stesso come input? le situazioni possibili sono due: 23

1. L’algoritmo “termina?” afferma che il nostro algoritmo in figura termina, e

conseguentemente (per come è definito) non termina l’esecuzione

2. L’algoritmo “termina?” afferma che il nostro algoritmo in figura non termina, e

conseguentemente (per come è definito) restituisce 0 e termina l’esecuzione

Quindi, il nostro algoritmo in figura avendo se stesso come input genera sempre una

contraddizione. Di conseguenza la risposta al problema della terminazione è che

l’algoritmo che verifica se un altro termina non può esistere

La macchina di Turing ha imposto dei limiti chiarissimi a quello che possiamo

calcolare e le analisi su essa effettuate hanno permesso di dimostrare che determinati

problemi computazionali interessanti, come quello della terminazione, non possono

essere risolti da nessun approccio algoritmico

Capitolo 3: Linguaggi di programmazione

Che cos’è un linguaggio?

Un linguaggio “naturale” è un linguaggio comune (come l’Italiano) che può essere

scritto o orale, e che si è evoluto in maniera naturale all’interno di una comunità. I

linguaggi naturali hanno il vantaggio (ma anche lo svantaggio) di essere così tanto

espressivi che specifiche istruzioni comunicate attraverso il loro uso possono sembrare

ambigue. Es: “la vecchia porta la sbarra”, si potrebbe trattare:

● Di una porta vecchia che sbarra il passaggio

o

● Di un’anziana signora che porta una sbarra

Spesso, tuttavia, riusciamo a disambiguare il significato di una frase, inserendola in un

contesto o con determinate convenzioni sociali.

I linguaggi naturali non sono formali, ma molti studi in linguistica cercano di fornire

una formalizzazione mediante l’uso di strumenti matematici. 24

Una delle figure più importanti della formalizzazione del linguaggio naturale è Noam

Chomsky, uno dei padri della linguistica moderna; le sue principali ipotesi di ricerca

sul linguaggio comune sono:

● La struttura sintattica di base, di un linguaggio naturale, è rappresentabile

mediante una teoria matematica.

● Tale struttura sintattica è determinata biologicamente in tutti gli esseri umani (è

già presente in noi sin dalla nascita) ed è una caratteristica unica dell’essere

umano che si è evoluta nel tempo.

Tra la sua produzione accademica troviamo la classificazione delle grammatiche

formali inserite all’interno di una gerarchia di crescente potere espressivo.

Grammatica formale

Essa è uno strumento matematico usato per definire la sintassi di un linguaggio

(naturale o artificiale) attraverso l’uso di un insieme finito di regole di produzione, che

permettono di costruire una qualunque frase valida in quello specifico linguaggio. Una

grammatica formale è composta da un insieme di regole di produzione di forma

premessa ::= espressione (in notazione Backus-Naur, o BNF). La premessa e

l’espressione possono contenere uno o più simboli delle seguenti tipologie:

● Terminale: specificato tra virgolette in BNF, che identifica tutti i simboli

elementari del linguaggio in considerazione (nomi, verbi, etc..)

● Non terminale: specificato tra parentesi angolari in BNF (<...>), che identifica

tutti i simboli di una grammatica formale che possono essere sostituiti da una

combinazione di terminali o non terminali

SCHEMA SEMPLIFICATO

1. Simboli terminali

● Sono gli elementi di base, cioè le "parole" vere e proprie del linguaggio.

● Non possono essere più scomposti.

● In BNF (Backus–Naur Form) si scrivono tra virgolette.

Esempio:

"ciao" "grazie" "se" "+" "1"

2. Simboli non terminali

● Sono categorie grammaticali o simboli che rappresentano strutture più 25

grandi.

● Possono essere sostituiti da altri terminali o non terminali.

● In BNF si scrivono tra parentesi angolari <...>.

Esempio:

<frase> <saluto> <espressione> <numero>

3. Regole di produzione

● Sono le istruzioni che dicono come costruire frasi corrette nel linguaggio.

● Ogni regola ha la forma:

<non-terminal> ::= <sequenza di simboli>

::=

(dove si legge “è definito come”)

Esempio di grammatica formale (BNF)

Immagina un mini-linguaggio che rappresenta saluti. La grammatica potrebbe essere

così:

<frase> ::= <saluto> <nome>

<saluto> ::= "ciao" | "buongiorno"

<nome> ::= "Anna" | "Luca"

Questa grammatica dice:

● Una frase è composta da un saluto seguito da un nome

"ciao" "buongiorno"

● I saluti validi sono o

"Anna" "Luca"

● I nomi validi sono o 26

La gerarchia proposta da Chomsky mette a disposizione un modo per descrivere

formalmente le relazioni che possono esistere tra diverse grammatiche in termini delle

loro possibili strutture sintattiche. Queste tipologie di grammatica sono elencate di

seguito, dalla meno espressiva alla più espressiva (vengono usate le lettere greche per

indicare qualsiasi possibile combinazione di simboli terminali e non, incluso il

simbolo terminale vuoto che viene indicato con ε):

Grammatiche regolari

Le grammatiche regolari sono le più semplici tra le grammatiche formali. Servono

per descrivere linguaggi molto semplici, come quelli che possono essere riconosciuti

da automi a stati finiti (tipo semafori, macchine con stati, ecc.).

Le regole che puoi usare in una grammatica regolare hanno solo due forme:

✅

1.

<non-terminale> ::= "terminale"

Significa: il simbolo non terminale può essere sostituito solo da un terminale (cioè

una "parola").

✅

2.

<non-terminale> ::= "terminale" <non-terminale>

Significa: il non terminale può essere sostituito da un terminale seguito da un altro

non terminale.

ESEMPIO

1. <frase> ::= "Io" <verbo>

2. <verbo> ::= "scrivo" oppure <verbo> ::= "leggo"

✅ Frasi valide con questa grammatica:

Io scrivo

● Io leggo

●

Queste due frasi seguono perfettamente le regole. 27

Grammatiche libere dal contesto

Una grammatica libera dal contesto (context-free grammar, CFG) è più potente

delle grammatiche regolari. Permette di descrivere strutture più complesse, come

frasi con soggetto + verbo + complemento, parentesi annidate, ecc.

La regola generale è:

<non-terminale> ::= γ

Dove γ può essere qualsiasi combinazione di simboli terminali e non terminali.

ESEMPIO

<frase> ::= <pronome> <frase-verbale>

Una frase è formata da un pronome seguito da una frase verbale

___________________________________________________________________

<pronome> ::= "Io"

Io"

Il pronome ammesso è solo "

___________________________________________________________________

<nome> ::= "libro"

<nome> ::= "documento"

libro"

Il nome può essere " o "documento"

___________________________________________________________________

<frase-verbale> ::= <verbo>

<frase-verbale> ::= <verbo> "un" <nome>

Una frase verbale può essere:

● solo un verbo (scrivo, leggo)

● oppure un verbo seguito da "un" e un nome (scrivo un libro, leggo un 28

documento)

✅ Frasi valide con questa grammatica:

Io scrivo

1. Io leggo

2. Io scrivo un libro

3. Io leggo un documento

4. Io leggo un libro

5.

Tutte queste frasi seguono perfettamente le regole

Grammatiche dipendenti dal contesto

Una grammatica dipendente dal contesto (context-sensitive grammar) può

esprimere frasi in cui certe parole dipendono da altre presenti nel contesto.

Permette di descrivere regole linguistiche più rigide o complesse, come l’accordo tra

soggetto e verbo, oppure cambiamenti che dipendono da dove si trova un simbolo.

La forma generale è:

α <non-terminale> β ::= α γ β

Cosa significa?

● Il non terminale può essere sostituito da γ, solo se si trova tra α e β.

● Quindi: la sostituzione dipende dal contesto.

Diversamente dalle grammatiche libere dal contesto, qui non si può sostituire

un simbolo isolato: bisogna tenere conto di cosa c’è prima e dopo.

1. Regola libera:

<frase> ::= <pronome-soggetto> <frase-verbale>

Una frase è composta da un soggetto e una frase verbale (come nelle 29

grammatiche precedenti).

2. Regola dipendente dal contesto:

"Io" <pronome-oggetto> <verbo> ::= "Io" <pronome-

oggetto> "amo"

Questa è una regola che cambia il verbo in "amo" solo se prima c’è "Io" e

subito dopo c’è un pronome oggetto.

Esempio:

Io ti scrivo Io ti amo

→ diventa

● perché "Io" + "ti" creano il

contesto per sostituire "scrivo"/"leggo" con "amo".

3. Altra regola contestuale:

"Io" <verbo> <nome> ::= "Io" "leggo" "un" <nome>

Questa regola dice: se "Io" è seguito da un verbo e un nome, allora va riscritto

Io leggo un <nome>

come:

Esempio:

Io scrivo libro Io leggo un libro

→ si può trasformare in

● grazie a questa regola.

5. Terminali:

<pronome-soggetto> ::= "Io"

<pronome-oggetto> ::= "ti" | "vi"

<nome> ::= "libro" | "documento"

Grammatiche ricorsivamente enumera