Materia:Linguaggi formali e automi

Da Wikiversità, l'università aperta.

Questa pagina contiene il testo delle lezioni legate alla materia generale, per una più agevole lettura necessita di essere divisa in lezioni.
Per una lista completa delle materie da suddividere in lezioni, consulta la relativa categoria.

Linguaggi formali e automi
Facoltà di Scienze matematiche, fisiche e naturali	Dipartimento di Informatica Tutte le lezioni in ordine alfabetico SSD = INF/01	Corso di Informatica

Presentazione Prerequisiti Rudimenti di insiemistica e logica matematica. Si attende che lo studente sia in grado di riconoscere la tipologia di un linguaggio, sappia costruire un semplice automa che lo genera a partire da una grammatica data e viceversa. Si attende anche che lo studente sia in grado di riconoscere i Linguaggi definiti dalle Espressioni Regolari ed elencati secondo le Gerarchie descritte da Chomsky. Obiettivi Il corso fornisce una presentazione teorica dei linguaggi formali e dei metodi per riconoscerli, generarli ed elaborarli. Si vorrebbe creare un corso che vada crescendo nelle conoscenze dello studente in maniera graduale, arrivando a spiegare i concetti formali come una conseguenza logica dello scibile. Alcune notazioni iniziali, potranno sembrare non corrette fino all'enunciato formale.	Programma Introduzioneai linguaggi formali Operazioni sul linguaggio formale Linguaggi regolari e liberi dal contesto Automi a stati deterministici e non deterministici Automi a stati e grammatiche di tipo 3 Automi a stati ed espressioni regolari Approcci di rappresentazione: generatori e riconoscitori Le grammatiche come sistema generativo Classificazione delle grammatiche Alberi di derivazione Grammatiche di tipo 2 ambigue e non Forme normali di Chomsky e di Greibach "Pumping lemma" e linguaggi non liberi dal contesto Riconoscitori per linguaggi liberi dal contesto
Risorse	Verifiche d'apprendimento È possibile, e fortemente consigliato, integrare le lezioni e valutare la propria preparazione attraverso queste esercitazioni. È possibile verificare la conoscenza di un argomento specifico o dell'intero programma.
Utenti interessati Modifica Al momento non ci sono utenti interessati alla materia.

Introduzione

Si vorrebbe creare un corso che vada crescendo nelle conoscenze dello studente in maniera graduale, arrivando a spiegare i concetti formali come una conseguenza logica dello scibile. Alcune notazioni iniziali, potranno sembrare non corrette fino all'enunciato formale.

Cominciamo..

Introduzione ai Linguaggi

Un Linguaggio Formale è definito come:

un insieme di stringhe di lunghezza finita costruite sopra un alfabeto finito,
cioè sopra un insieme finito di oggetti tendenzialmente semplici che vengono chiamati caratteri, simboli o lettere.

Nel corso di Fondamenti di Informatica, cosi' come nei Laboratori di Programmazione, abbiamo anche osservato che nel nostro computer utilizziamo un alfabeto chiamato ASCII, ad esempio. Esso é fatto degli stessi simboli che compongono le parole di questo testo. :)

Per poter capire quello scritto, così come quello parlato, é necessario riconoscerlo.

Noi tutti siamo automi in grado di riconoscere il nostro linguaggio (italiano) fatto di simboli (lettere | 'a','b','c',..)
che compongono parole (stringhe | "casa","mucca","paletto",..)

Stare zitti (stringa vuota), e' uguale per qualsiasi linguaggio!!
(Anche in Burundi per non dire nulla si sta' zitti :) )

Abbiamo pertanto chiarito i seguenti punti :

• Un Linguaggio e' un insieme di elementi riconoscibili da un Automa
• Una concatenazione degli elementi dell'insieme Linguaggio e' definito "Stringa".
• Esiste un elemento dell'insieme (epsilon - definito Stringa Vuota) che appartiene all'insieme di tutti i linguaggi.

Gli Automi

Ora che sappiamo che cosa é un Linguaggio, abbiamo scoperto che é accettato da un Automa. (Quello che eravamo noi qualche riga fa..) Cosa sia un Automa, però é necessario non sia una definizione ambigua.

Un automa e' un meccanismo in grado di eseguire un confronto su un input dato
e modificare il suo stato interno fino a produrre un eventuale output.

Definiamo eventuale perché ricordiamoci che tacere equivale ad accettare un linguaggio qualsiasi ma non interagire, produrre un ouput di accettazione,in ogni caso. (Chi tace acconsente)

Come ultimo esempio su noi stessi,
ecco come viene modificato uno dei vostri stati interni riconoscendo la stringa

Si scherza, ovviamente..

Questo per indurre lo studente ad osservare che gli automi di cui si vuole parlare sono macchine che possiedono degli stati interni che, in base ad un input esterno, possono essere percorsi fino ad indurre l'Automa in un particolare stato.

Per poter chiarire meglio, evitando di fare esempi che possano involontariamente offendere il lettore :) , utilizzeremo l'esempio reale della macchina del caffè.

Definizione di Automa

Un automa é un oggetto composto di una quintupla così descritta:

• Un insieme di stati
• L'Automa deve potersi trovare in stati definiti dalle varie combinazioni di input. La funzione di transizione consente all'Automa di modificare il suo stato interno.

  
  

• Un Alfabeto di Input
• Il cambiamento degli stati interni avviene su una serie di Input. I Simboli in input devono appartenere al Linguaggio che l'Automa e' in grado di riconoscere.

  
  

• Una funzione di transizione
• La funzione di transizione definisce come cambi lo stato interno dell'Automa in fuzione dello stato in cui esso si trovi al momento del nuovo input.

  
  

• Lo stato Iniziale
• Il primo degli stati dell'Automa.

  
  

• Un insieme di stati particolari (definiti accettanti)
• Nell'insieme degli stati interni é possibile definirne alcuni che sono particolari. Questi sono gli stati accettanti; ovvero quegli stati in cui l'automa produce un output positivo (o accettante).

La Macchina del Caffè

Siamo circondati di diversi automi che incontriamo nella vita quotidiana e che non ci soffermiamo mai ad osservare. Tra i tanti, potremo citare lo sportello di una banca, o il distributore di sigarette, o quello di medicinali. Pensando all'Automa "MacchinaDelCaffè" possiamo immaginare che essa abbia:

• Un insieme di stati
• Ad esempio gli stati che sono necessari per riconoscere un valore introdotto di 35 cents (costo del caffè?)

  
  

• Un Alfabeto in Input
• L'Automa deve riconoscere le monete da 5, 10 o 20 centesimi. Qualora, didatticamente, non considerassimo la possibilità di accettare monete da 50€/cents, potremmo benissimo definire l'Alfabeto con i simboli { 5, 10, 20 }

  
  

• Una funzione di transizione
• L'inserimento delle monete provoca la modifica dello stato interno all'automa. Banalmente essa é in grado si sapere quanto credito é stato inserito.

  
  

• Uno stato iniziale
• La macchina é accesa e pronta. Il credito é pari a 0 (zero)

  
  

• Un insieme di stati accettanti
• Tutti gli stati interni per cui é possibile produrre un output. (Ovvero: Credito >= Costo Caffè)

Tra i vari strumenti di cui possiamo godere nella Rete, esiste JFlap che ci consente di poter illustrare in un modo più diretto questo tipo di oggetti che sono gli Automi.

Linguaggi e Operazioni

Questa lezione è solo un abbozzo. Se puoi contribuisci adesso a migliorarla secondo le convenzioni di Wikiversità.
Per l'elenco completo degli stub, vedi la relativa categoria

Gli Automi semplici come quelli appena descritti, possono formare delle strutture piu' complesse. Le operazioni che sono eseguibili sui Linguaggi riconsosciuti dagli Automi sono le seguenti:

• Unione
• Unire due Liguaggi significa farne l'unione insiemistica. L'insieme Unione dei linguaggi é composto da tutte le stringhe che compongono il primo ovvero il secondo.

  
  

• Concatenazione
• E' una operazione non commutativa che significa farne seguire una stringa del primo al secondo.

  
  

• Chiusura di Kleene
• E' un'operazione che definisce un insieme particolare delle Stringhe di un Linguaggio. Questo insieme di stringhe é quello che é possibile generare concatenando due stringhe di L, anche con ripetizioni.

  Ad esempio, se L fosse il Linguaggio dei caratteri Italiani e le due stringhe fossero "ba" e "da", l'insieme Chiusura troverá al suo interno parole come "sbadato", "badante" ma anche "badaba", "dabadaba" etc..

Esempi di chiusura:

• L = PHI (il Linguaggio Vuoto)
• L0 = epsilon (la Stringa Vuota)

Linguaggi Context-Free e Non Context-Free

Questa lezione è solo un abbozzo. Se puoi contribuisci adesso a migliorarla secondo le convenzioni di Wikiversità.
Per l'elenco completo degli stub, vedi la relativa categoria

Giunti fin quì possiamo dire che esistono due grosse categorie di Linguaggi, quelli che dipendono dal contesto e quelli che non. Le stringhe in sequenza "if" "then" "else" ci suggeriscono delle azioni che possono benissimo essere indipendenti da quello che stiamo in questo momento facendo. Stringhe invece come "salta" definiscono la necessità di poter avere quantomeno un posto dal quale saltare.

Definiamo un Linguaggio libero dal contesto (Context-Free) il primo.

Tutti quei Linguaggi che non sono come il primo dei due descritti, invece, sono linguaggi NON LIBERI dal contesto (Non Context-Free).

Giocare con i Linguaggi

Abbiamo delineato al meglio quello che un Linguaggio é nella nostra rappresentazione quotidiana. Siamo arrivati ad un bivio rappresentato da quello che nel quotidiano di un informatico é rappresentato dalle due caratteristiche che l'informatica: l'Hardware ed il Software.

Per comodidà di ragionamento, possiamo accostare l'idea di un apparecchio che sia in grado di riconoscere il Linguaggio che stiamo trattando a quello che é il concetto di Hardware. Se invece osserviamo il Linguaggio da un punto di vista più teorico, utilizziamo uno strumento software rapprasentato dalle Espressioni Regolari.

Entrambe le vie descritte portano alla trattazione di Linguaggi.

Quale linguaggio?

Nel discorso che abbiamo appena ultimato abbiamo chiarito in modo univoco che cosa siano gli automi ed i Linguaggi che questi automi riconoscono. Un altro modo per chiarire al meglio un Linguaggio é quello di descriverlo con una Espressione Regolare (RE - Regular Expression).

In entrambi i modi siamo in grado di identificare il Linguaggio che andiamo a "disegnare", ma con una grossa differenza: mentre un Automa é quello strumento che ci consente di riconoscere un Linguaggio, l'espressione regolare é quello strumento che ci permette di descriverlo.

Riconoscere un Linguaggio

Descriviamo di seguito i modi di riconoscere un Linguaggio. Per fare questo abbiamo la necessità di osservare meglio gli Automi che abbiamo utilizzato inizialmente (es: Macchina del Caffè).

Automi

Questa lezione è solo un abbozzo. Se puoi contribuisci adesso a migliorarla secondo le convenzioni di Wikiversità.
Per l'elenco completo degli stub, vedi la relativa categoria

Quando abbiamo definito che cosa sia un Automa non ci siamo soffermati in modo appropriato su alcune caratteristiche che questo oggetto possiede.

Scopriamo che l'insieme degli stati di un Automa può essere particolare. Questo insieme di stati può essere univoco (e questo non ci sorprende) ma potremmo anche creare un automa in grado di stare in uno stesso tempo in più stati!! Immaginiamo di utilizzare ad esempio un Automa che cerchi di capire se la stringa in ingresso

Ipotiziamo di avere il seguente Alfabeto : E = { 0, 1 }

Cerchiamo di trovare la stringa che appartenga al Linguaggio tale che:

• Il numero degli ZERI (0) sia un numero dispari
• Il valore decimale del numero indicato sia pari

Automi a Stati Finiti

Automi a Stati NON Finiti

Automi con transizioni Epsilon

Descrivere un Linguaggio

Questa lezione è solo un abbozzo. Se puoi contribuisci adesso a migliorarla secondo le convenzioni di Wikiversità.
Per l'elenco completo degli stub, vedi la relativa categoria

Il Linguaggio che é in grado di riconoscere un Automa può benissimo essere descritto con delle semplici Espressioni Regolari. Chi utilizza strumenti liberi quali GNU/LINUX potrebbe avere maggiore confidenza con questo modo di descrivere un Linguaggio. Infatti chi utilizza GNU/LINUX, piuttosto che Microsoft Windows può trovare più intellegibile l'espressione:

      mac*

Questa cosa scritta sopra é una Espressione Regolare. Rappresenta tutte quelle stringhe che iniziano con le lettere 'mac' e che continua con qualsiasi altro carattere. A questa espressione possono fare riferimento nome files (ad esempio) che si chiamino 'mac.jpg', 'machighine', 'macellaio', 'mac', e così via, via discorrendo...

Espressione Regolare (RE)

Una Espressione Regolare, così come indicato dal nome, é una espressione che descrive il tipo di stringa che possiamo aspettarci di trovare nel Linguaggio che essa descrive.

Esistono dei caratteri speciali per .....

Modi di Scrivere

Pumpkin Lemma