LFA - Linguaggi Formali Autonomi

LINGUAGGI FORMALI E AUTONOMI

CAPITOLO 1: LINGUAGGI E GRAMMATICHE

ALFABETO, PAROLA, LINGUAGGIO

Linguaggio​ insieme di frasi che permette la comunicazione tra più entità. Per specificare un linguaggio

abbiamo bisogno di due cose:

vocabolario - elenco di vocaboli appartenenti al linguaggio;

● sintassi - regole con le quali si compongono i linguaggi, regole semantiche.

●

Formale​ ​specifica rigorosa e precisa dei linguaggi mediante l’utilizzo di strumenti matematici

Automa​ ​macchina che consente di stabilire se una frase appartiene o meno ad un determinato

linguaggio formale.

I linguaggi verranno formalizzati mediante:

sistemi generativi​

: ​un esempio di sistema generativo è dato dalle grammatiche, per formalizzare un

● linguaggio vengono fornite delle regole;

sistema riconoscitivo​ : ​un esempio di sistema riconoscitivo è dato dagli automi, attraverso delle

● macchine, infatti, si può comprendere il linguaggio formale;

Simbolo​ un qualsiasi oggetto rappresentativo.

Alfabeto​ ​ i

​ nsieme finito di simboli Σ = {a , .

.., a }

n

1

Esempio​ : ​alfabeto binario costituito da solo due simboli, quali: Σ = {a, b} Σ = {0, 1} Σ = {(, )}

Parola​ ​ (o stringa ) su un alfabeto Σ è una sequenza finita di simboli appartenenti a Σ

ω

Esempi​ :

● Σ = {a} ω = a

, aa, aaa

● Σ = {0, 1

} ω = 0

, 1, 000, 1010

Parola vuota​ :​ Lunghezza di una parola​

:

ε |

ω |

+

=

​ insieme delle parole su Σ compresa ​ = insieme delle parole su Σ senza =

* *

Σ Σ Σ

ε ε ∖{ε}

Prodotto di giustapposizione

Date si dice ​ prodotto di giustapposizione​ la parola dove

*

x

, y Σ z = x · y = x x ...x y y ...y x = x x ...x

∈ 1 2 k 1 2 k 1 2 k

′

e y = x y y ...y

k 1 2 k ′

Proprietà del prodotto​:

chiuso rispetto a *

● Σ

associativo

● elemento neutro

●

Lunghezza del prodotto​

: Elemento neutro:​

|

x · y| = |

x

| + |

y | e · x = x · e = x e = ε

Allora ​ è un monoide dove:

*

(Σ , ·

, ε)

= insieme di parole

*

● Σ

= operazione binaria associativa

● · = elemento neutro

● ε

Scomposizione di parole:​ *

x

, ω Σ

∈

è p

​ refisso​ di se per qualche

● x ω ω = x · y y

è s

​ uffisso​ di se per qualche

● x ω ω = y · x y

è f

​ attore​ di se per qualche

● x ω = z · x · y y , z

NOTA:​ sono contemporaneamente prefisso, suffisso e fattore di

ω , ε ω

Un l

​ inguaggio​ L sull’alfabeto è un insieme di parole di , cioè un qualunque sottoinsieme (finito o

*

Σ Σ

infinito) . Si distinguono quattro tipologie di linguaggi:

*

L Σ

⊆

1. ∅:​ ​è il linguaggio vuoto, la sua cardinalità è zero, è il linguaggio privo di qualsiasi elemento;

2. {ε}:​ ​è il linguaggio di la sua cardinalità è uno, è il linguaggio composto solo dalla parola vuota;

ε,

3. Finito​

: ​è il linguaggio a cardinalità finita, ossia composto da un numero finito di elementi;

Esempi ∅ è un linguaggio finito di cardinalità uguale a zero

● {ε} è un linguaggio finito di cardinalità uguale ad uno

● L = {ε, a, aa, aaa} è un linguaggio finito di cardinalità uguale a quattro

●

4. Infinito​ :​ ​è il linguaggio a cardinalità infinita, ossia composto da un numero di elementi innumerabile;

Esempi {a}*, precisando che con questa scrittura s’intende l’insieme di tutte le parole che si possono

● costruire a partire dall’alfabeto costituito dal singolo simbolo ‘a’, bisogna considerare il fatto

che l’insieme di parole costruibili a partire da un alfabeto unitario ha cardinalità infinita,

infatti: {a}* = {ε, a, aa, aaa, aaaa, aaaaa, ...} = {ε, a​ , a​ , a​ , a​ , ...}

1​ 2​ 3​ 4​

Le espressioni booleane sulle operazioni ¬, ^,∨: definiamo allora

● Σ = {

0, 1, , , ¬, (, )}

⋀ ⋁

L come il linguaggio delle espressioni booleane; Regole:

0 L, 1 L

○ ∈ ∈

se allora

○ x

, y E (

x y), (x y), ¬

x E

∈ ⋀ ⋁ ∈

Nient’altro appartiene a L s

○

OPERAZIONI TRA LINGUAGGI

Unione​ Osservazione: A , B .

*

● A B = {

w Σ | w A w B} A B A B

⋃ ∈ ∈ ⋁ ∈ ⊆ ⋃ ⊆ ⋃

Esempio​ : ​Sia Σ = {0, 1} A = {w Σ* | prefisso w = 1} = 1 {0, 1}* e B = {w Σ* | suffisso w = 0} =

∈ ∈

{0, 1}* 0, A B = {parole su Σ | prefisso = 1 oppure suffisso = 0} = 1 {0, 1}* oppure {0, 1}* 0

∪

Intersezione​ Osservazione: A B A, A B B.

*

● A B = {

w Σ | w A w B}

⋂ ∈ ∈ ⋀ ∈ ∩ ⊆ ∩ ⊆

Esempio​ : ​Sia Σ = {0, 1} A = 1 {0, 1}* e B = {0, 1}* 0, A B = {parole su Σ | prefisso = 1 e suffisso

∩

= 0} = 1 {0, 1}* 0

c

Complemento​ Osservazione: A A​ = ∅.

* C ​

● A = {

w Σ | w A}

∈ ∉ ∩

Esempio​ : ​Σ = {0, 1} A = 1 {0, 1}, A​ = {parole su Σ | prefisso ≠ 1} = 0 {0, 1}*

C ​

Prodotto​ Osservazione: non è commutativo

*

● A · B = {

xy Σ | x A x B } A · B

∈ ∈ ⋀ ∈

Esempio​ : ​A = {a}* = {ε, a, aa, aaa , ...} e B = {b}* = {ε, b, bb, bbb​ ​, ...}, = {w Σ*| w = xy dove x

A · B ∈

A e y B} = a*b*

∈ ∈

k 0 k k−1

Potenza​ oppure = { } e =

● L = L · L · .

.. · L L L L L

ε ⋅

Esempio​ : ​L = {a} , L​ = { w | w {a, b}* dove |w| = k }, L​ = {w | w {a, b }* dove |w| = 5 }

k ​ 5 ​

∈ ∈

Chiusura di Kleene

● ∞

∪

0 1 k k

*

L = L L = L

⋃ ∪...∪L ∪... k=0

∞

∪

+ k n n−1 0

dove e, per convenzione, .

L = L L = L L = ε

⋅L

k=1

Esempio​ : ​L = {a, bb}, L* = L​ L​ L​ ... L​ ... L​ = {a, bb}*

0 ​ 1 ​ 2 ​ k ​ ∞ ​

∪ ∪ ∪ ∪ ∪ ∪

CODICI +

Un linguaggio L è un c

​ odice​ quando ogni parola in può essere decomposta in maniera univoca, come

L

prodotto di parole di L. I codici NON contengono L è un​ codice prefisso​ quando:

ε.

è un codice

● ogni parola in L non è prefisso di altre parole in L

●

Esempio di codice prefisso

L = {aa, aba, baa}, x = “baaabaaabaa”, x L​ decomposizione: baa aba aa baa L​

+ ​ +

∈ ⋅ ⋅ ⋅ ∈

Non sono possibili altre decomposizioni di x in L, quindi L è un codice, altresì L è un “codice prefisso” in

quanto ciascuna parola non è prefisso di nessun’altra parola di L.

Esempio di codice non prefisso

C = {0, 01}, y = “00010101”, y C​ decomposizione: 0 0 01 01 01 C​

+ ​ +

∈ ⋅ ⋅ ⋅ ⋅ ∈

Non sono possibili altre decomposizioni in C quindi è un codice. la parola “0” C è prefisso della parola

∈

“01” C, quindi, nonostante sia un codice, non è un “codice prefisso”

∈

Esempio di non codice

L = {bab, aba, ab}, k = “ababab”, k L​ decomposizione: ab ab L​ oppure aba bab L​

+ ​ + ​ +

∈ ⋅ ⋅ab ∈ ⋅ ∈

sono possibili più decomposizioni quindi L non è un codice

RAPPRESENTAZIONE DI LINGUAGGI

Un linguaggio L è un insieme di parole su un dato alfabeto. Abbiamo due rappresentazioni:

Estensiva​ solo se L è finito

● L = {

w , w , .

.., w }

n

1 2

Intensiva​ dove P è una proprietà e vale per ogni L anche infinito

*

● L = {

w Σ | P (w) = 1

}

∈

I linguaggi infiniti, se ammettono una descrizione, possono essere descritti con due sistemi diversi:

Sistemi riconoscitivi ​ permettono di stabilire, data una parola, se essa appartiene o meno al

● linguaggio. I linguaggi che ammettono un sistema riconoscitivo sono detti “linguaggi ricorsivi” o

“decidibili”, i più comuni sistemi riconoscitivi sono gli “automi a stati finiti” e “automi a pila”,

capaci di riconoscere due sottoclassi di linguaggi ricorsivi, detti rispettivamente “linguaggi

regolari” e “linguaggi liberi da contesto”.

Sistemi generativi​ ​permettono di costruire parole del linguaggio (grammatiche);

●

SISTEMI RICONOSCITIVI

Un sistema riconoscitivo per il linguaggio L Σ*, è in grado di calcolare, mediante un algoritmo

⊆

“​

riconoscitore​ ”, la funzione caratteristica del linguaggio.

Funzione caratteristica​ : la funzione che ci permette di individuare, fornita una parola in ingresso, se la parola

appartiene o meno al linguaggio L, cioè la funzione tale che = 1 se x L, 0 altrimenti

χ χ (x) ∈

L L

PROCEDURE E ALGORITMI

Procedura​ s

​ equenza finita di istruzioni che possono essere eseguite automaticamente e che possono portare

ad un risultato se il programma è progettato per fornirlo.

Algoritmo​ procedura che termina sempre, qualsiasi sia l’input fornitogli in ingresso, un algoritmo non

prevede quindi situazioni di loop infiniti o di break;

Programma​ strumento mediante il quale vengono definite le procedure e gli algoritmi. I programmi

hanno quattro diversi punti di vista che li descrivono:

Sintattico​

: ​un programma è una parola w {0, 1}* ossia una sequenza di bit, questa connotazione

● ∈

fornisce la descrizione del programma w mediante la sua codifica ASCII, un programma viene quindi

inteso sintatticamente come un insieme di parole su Σ* dove Σ* è l’alfabeto binario formato solo da

“0” e “1”;

Semantico​ :​ ​un programma “w” è una procedura che, opportunamente inizializzata, genera una

● sequenza di passi di calcolo che possono terminare fornendo un risultato, indichiamo con

la semantica del programma, dove “w” sintatticamente è una parola binaria che

○ F ω

corrisponde al codice ASCII di un programma e “x” è sintatticamente una parola binaria

che viene passata come dato input al programma

il risultato del programma su input *

○ F (x) ω x {

0, 1

}

∈

ω

Non terminano​ :​ ​sono programmi che vanno in loop, il risultato dell’esecuzione di questa tipologia di

● programma viene indicato con Fw(x)↑, che indica che il programma w su input x non termina.

Terminano​

:​ s

​ ono programmi che terminano la loro esecuzione fornendo come output solo due

● tipologie di valori: 0 o 1, il risultato dell’esecuzione di questa tipologia di programma viene indicato

con indica che su input termina, in particolare, si ha il caso se la procedura dà

F (x)↓ ω x F (x) = 1

ω ω

in uscita 1, mentre se la procedura dà in uscita 0.

F (x) = 0

ω

Interprete​ i

​ ndicato con u, è un programma che prende in input un altro programma w ed un dato x, fornendo

in output il risultato che ottiene simulando l’esecuzione del programma w sul dato x, ossia l’interprete

fornisce in output , se w è un programma, in caso contrario ritornerà quale uscita un indefinito (⊥).

F (x)

ω

Input di u​

:​ x

​ , w {0, 1}* dove x è un dato e w è un programma;

● ∈

Esecuzione di u:​ ​l’interprete, avendo come ingresso la parola x$w, simula l’esecuzione della

● procedura codificata con il programma w su ingresso del dato x, detta simulazione viene

rappresentata dalla dicitura o

F (x, ω

) F (x$ω)

u u

Output di u​

:​ i

​ l risultato dell’interprete può assumere due valori distinti

● sse w è un programma

○ F (x)

ω sse w non è un programma

○ F (x, ω

) ↑

u

LINGUAGGI RICORSIVI E RICORSIVAMENTE ENUMERABILI

Un linguaggio L è detto ​ ricorsivo​ se esiste un algoritmo implementato dal programma tale che,

ω

passandogli in input un dato x {0, 1}*​ ​ tale che e .

F (x) = 1 se x L F (x) = 0 se x / L

∈ ∈ ∈

w w

Se L è ricorsivo allora ho un programma w che termina sempre, in quanto implementa un algoritmo, e come

abbiamo visto, l’algoritmo mi garantisce sempre che il programma restituirà un risultato dalla sua esecuzione.

Un linguaggio ricorsivo può essere specificato con una quantità finita di informazioni; essa è data dal testo w

del programma che calcola la funzione caratteristica di L, un linguaggio ricorsivo è quindi un linguaggio che

ammette un sistema riconoscitivo. Inoltre, dato x Σ*, risulta possibile decidere se x L semplicemente

∈ ∈

eseguendo il programma w su ingresso x e recuperando il risultato dopo un numero finito di passi di calcolo.

Quindi se L è ricorsivo si dice d

​ ecidibile e

​ L ammette un sistema riconoscitivo.

P L

Un linguaggio L è detto ​ ricorsivamente enumerabile​ se esiste una procedura implementata dal

programma ​ tale che, passandogli in input un dato x {0 ,1}*, e .

ω F (x) = 1 se x L F (x)↑ se x / L

∈ ∈ ∈

w w

Se L è ricorsivamente numerabile allora ho un programma w che non termina sempre, infatti implementa

una procedura, e come abbiamo visto, la procedura non mi garantisce la terminazione del programma.

Un linguaggio ricorsivamente numerabile può essere specificato con una quantità finita di informazioni; essa

è data dal testo w del programma che risponde 1 quando x L e non termina l’esecuzione quando x L.

∈ ∉

contrariamente a quanto accade per i linguaggi ricorsivi, nei linguaggi ricorsivamente numerabili, quando x ∉

L non è possibile recuperare l’informazione in un numero finito di passi di calcolo, se ne conclude quindi che

un linguaggio ricorsivamente numerabile non ammette un sistema conoscitivo bensì solo un sistema

generativo. Inoltre, dato x Σ*, non risulta sempre possibile decidere se x L semplicemente eseguendo il

∈ ∈

programma w su ingresso x e recuperando il risultato, infatti, se x L il programma, dopo un numero finito

∈

di passi di calcolo, fornirà in uscita il risultato, in caso contrario, se x L, il programma entrerà in loop senza

∉

fornire alcun risultato. Quindi se L è ricorsivamente enumerabile allora si dice s

​ emidecidibile e

​ L ammette

P L

un sistema generativo.

TEORIA DEI LINGUAGGI

Linguaggio = Problema​ :​ ​studiare un linguaggio significa studiare e risolvere un problema, infatti, associato a

ciascun linguaggio esiste un problema, che indicheremo con la dicitura P​ , in generale infatti un linguaggio L

L​

può essere descritto mediante la seguente proprietà: L = {w | P(w) = 1} ossia, il linguaggio L è costituito da

quelle parole w tali che soddisfino la proprietà P, dove dire che w soddisfa P è analogo a scrivere P(w) = 1.

Se L è un linguaggio ricorsivo, il problema P​ associato al linguaggio prende il nome di ​ decidibile​ ,

● L ​

ossia​ è un problema risolvibile interamente in maniera automatica. L ricorsivo P​ decidibile;

↔

​ L ​

Se L è un linguaggio ricorsivamente numerabile, il problema P​ associato al linguaggio prende il

● L ​

nome di s

​ emidecidibile​ , ossia è un problema risolvibile in maniera automatica solo parzialmente. L

ricorsivamente numerabile P​ semidecidibile.

↔ L​

P​ è così definito:

L​ ​ in input abbiamo delle parole binarie, w {0, 1}*

● ∈

in output abbiamo la risposta SI/NO associata alla seguente domanda: “w soddisfa P?” dato un

● problema P​ codifico ogni istanza del problema P​ in un’istanza binaria e poi mi pongo la domanda,

L, ​ L​

ossia creo un algoritmo A per PL, dove A è un algoritmo che stabilisce se w L restituendo 1 o 0 in

∈

base all’appartenenza o non appartenenza della parola w al linguaggio L.

Se w allora, dato che L = {w | P(w) = 1} w soddisfa anche P​

∈L L

Se w allora, dato che L = {w | P(w) = 1} w non soddisfa neanche P​

∉L L

C

Teorema: L ricorsivo L ricorsivo

⇒

Se L è un linguaggio ricorsivo, allora esiste un algoritmo implementato dal programma A tale che,

passandogli in input un dato x {0, 1}*: F​ (x) = 1 sse x L​ F​ (x) = 0 sse x L.

∈ ∈ ∉

A​ ​ B​

Invece, L​ = {w Σ* | w L} si necessita quindi di un secondo programma B tale che, passandogli in

C ​ ∈ ∉

input un dato x {0, 1}*: F​ (x) = 0 sse x L F​ (x) = 1 sse x L.

∈ ∈ ∉

B​ B​

Dato che, se x L, F​ (x) = 1 e, se x L, F​ (x) = 0, allora possiamo pensare che B è un programma che​

∈ ∉

A​ A​ ,

passandogli in input il risultato per programma A (FA(x)) si comporta nella seguente maniera:

F​ (x) = 0 sse FA(x) = 1​ F​ (x) = 1 sse FA(x) = 0.​ Vediamo ora in dettaglio i due programmi A e B e le

B​ ​ B​ ​

modifiche che si necessita