Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
vuoi
o PayPal
tutte le volte che vuoi
Grammatiche di Chomsky
Le grammatiche che andremo ad utilizzare sono dette grammatiche di Chomsky perché furono introdotte appunto da Noam Chomsky per rappresentare i procedimenti sintattici elementari che sono alla base della costruzione di frasi della lingua inglese.Grammatiche di tipo 0 limitate
Le grammatiche di tipo 0, dette anche non definiscono la classe di linguaggi più ampia possibile. In esse le produzioni sono del tipo più generale: V = NT U Tv -> w con v V* * NT * V* e w V* ∈ ∈ Queste grammatiche ammettono anche derivazioni che accorciano le forme di frase, cioè con le ε-produzioni. I linguaggi generabili da grammatiche di tipo 0 si dicono linguaggi di tipo 0.Grammatiche di tipo 1
Queste grammatiche, dette anche contestuali o context-sensitive, ammettono qualunque regola di produzione che non riduca la lunghezza delle stringhe, cioè del tipo: v -> w con v V* NT V* e w V con |v| <= |w|+∈ ∈ Esempio: S ->aSa | aAb | aAaaA -> aaAb ->aab
Appartiene ad una grammatica di tipo 1. Non accettano ε-produzioni.
Page 10 of 56
Grammatiche di tipo 2 non contestuali,
Queste grammatiche, dette anche libere dal contesto, ammettono produzioni del tipo:
A -> w con A NT e w V + ∈ ∈ w
Cioè produzioni in cui ogni non terminale A può essere riscritto in una stringa indipendentemente dal contesto in cui esso si trova. Esempio: S -> aSb | ab.
Non accetta ε-produzioni.
Grammatiche di tipo 3 destre o regolari
Queste grammatiche, dette anche regolari, ammettono produzioni del tipo:
A -> w con A NT e w ( T * NT ) U T ∈ ∈
Il termine regolare deriva dal fatto che tali linguaggi sono rappresentabili per mezzo di espressioni regolari. Il termine lineare invece deriva dal fatto che al lato destro di ogni produzione compare al più un simbolo non terminale.
Grammatiche lineari destre cioè che crescono verso destra: S -> aS | b
Grammatiche lineari sinistre cioè che
crescono verso sinistra: S -> Ab | b. A -> Aa | a
Vedremo che per ogni grammatica lineare destra ne esiste una equivalente sinistra. Quindi si verifica immediatamente che per ogni 0 <= n <= 2 ogni grammatica di tipo n +1 è anche di tipo n e pertanto l’insieme dei linguaggi di tipo n contiene tutti i linguaggi di gerarchia di Chomsky. Tipo n+1 formando una gerarchia detta [Tipo 0 [ Tipo 1 [ Tipo 2 [ Tipo 3 ] ] ] ]
Quindi un linguaggio L viene detto strettamente di tipo n se esiste una grammatica G di tipo n e non esiste alcuna grammatica G’ di tipo m > n che possa generarlo.
Forma normale di Backus
Abbiamo visto che le grammatiche formali possono essere utilizzate per la definizione di linguaggi di programmazione. Per la definizione sintattica dei linguaggi di programmazione vengono adottate grammatiche non contestuali tradizionalmente forma normale di Backus-rappresentate mediante una notazione specifica denominata Naur o BNF. Questa notazione è usata per
Grammatiche content-free usando:
- I simboli terminali sono sempre costituiti da stringhe racchiuse tra parentesi acute <…>
- Il segno di produzione -> viene sostituito dal simbolo ::=
- Le parentesi graffe vengono impiegate per indicare l'iterazione illimitata (0, 1,…. n) volte
- E analogamente { } ^ 5 indica l'iterazione per un numero di volte pari al più ad n.
Es: A ::= bA | a si può riscrivere come A ::= { A } a
Le parentesi quadre [ … ] vengono usate per indicare l'opzionalità.
Es: A ::= xy | y si può scrivere come A ::= [ x ] y
Le parentesi tonde ( … ) vengono usate per indicare la fattorizzazione cioè la messa in comune di una sottoespressione.
Es: A ::= xu | xy | xc si può riscrivere come A ::= x ( u | y | c )
Page 11 of 56
Espressioni regolari
Le espressioni regolari sono dei formalismi che ci permettono di definire certi tipi di linguaggi.
Sia Σ un alfabeto finito.
L'insieme delle espressioni regolari su Σ è costituito da tutte le espressioni generate induttivamente come segue.
ε è un'espressione regolare che denota il linguaggio { ε }
Se a è un simbolo di Σ allora a è un'espressione regolare che denota il linguaggio { a }
Siano r e s due espressioni regolari che denotano i linguaggi L( r ) e L( s ) allora:
- ( r ) | ( s ) è un'espressione regolare che denota il linguaggio L( r ) U L( s )
- ( r ) ( s ) è un'espressione regolare che denota il linguaggio L( r ) L( s )
- ( r )* è un'espressione regolare che denota il linguaggio L( r )*
- ( r ) è un'espressione regolare che denota il linguaggio L( r )
Un linguaggio denotato da un'espressione regolare viene chiamato insieme regolare.
Accettazione e riconoscimento dei linguaggi
Le grammatiche formali costituiscono uno strumento generativo per la rappresentazione
La classificazione dei linguaggi tuttavia non consente di impostare in modo algoritmico il problema del riconoscimento di un linguaggio, cioè di decidere, dato un linguaggio L e una stringa x, se x appartiene a L. Tale problema riveste un'importanza fondamentale in quanto è un problema che si affronta nel riconoscimento di linguaggi di programmazione.
Il concetto fondamentale per quanto riguarda il riconoscimento dei linguaggi è il concetto di automa, inteso come dispositivo astratto che, dato una stringa x in input, può eseguire una computazione e, eventualmente, restituire un valore booleano se la computazione termina. In generale, la struttura di un automa comprende un dispositivo interno che ad ogni istante assume uno stato che rappresenta l'informazione associata al funzionamento interno.
Inoltre, un automa può utilizzare uno o più dispositivi di memoria sui quali è possibile memorizzare informazioni durante la computazione.
delle informazioni sotto forma di stringhe di caratteri da alfabeti anch'essi predefiniti. Tali dispositivi si suppone siano dei nastri cioè sequenze di celle di memoria. Il configurazione funzionamento di una automa è quindi definito rispetto ai due concetti di e funzione di transizione. La configurazione è composta dallo:
- Stato interno dell'automa
- Contenuto dei registri di memoria
- Posizione di tutte le testine sui nastri
- funzione di transizione
La invece induce una relazione di transizione tra diverse configurazioni cioè l'associazione ad una configurazione un altra configurazione detta successiva. L'applicazione di una funzione di transizione ad una configurazione si dice transizione o mossa o passo computazionale dell'automa.
Automi a stati finiti Gli automi di questo tipo non possono memorizzare informazioni a parte la stringa di input inoltre il nastro contenente la stringa di input può essere scandito
dalla relativa testina unasola volta. La funzione di transizione per questo tipo di automi associa al carattere lettoun nuovo stato in maniera tale da associare alla configurazione attuale la configurazionesuccessiva. Questo viene rappresentato tramite un diagramma di transizione che è ungrafo orientato i cui nodi rappresentano gli stati mentre gli archi, etichettati con i simbolidell'alfabeto di input, rappresentano le possibili transizioni tra stati. Alcuni nodi sono
opportunamente contrassegnati come finali mentre un solo nodo è contrassegnato comeiniziale.
Automi a stati finiti non deterministici
Sia automi deterministici che non deterministici hanno la stessa potenza cioè quelle diriconoscere esattamente la classe dei linguaggi regolari cioè i linguaggi definiti daespressioni regolari.
Un automa finito o a stati finiti non deterministico ( NFA ) è una quintupla:< Σ , Q , δ , q , F >0
Dove:Σ è una
alfabeto finito cioè i simboli di input•
Q è un insieme finito di stati•
δ è la funzione di transizione cosi definita: δ : Q x ( Σ U { ε } ) -> P( Q )•
dunque associa un insieme di stati ad ogni coppia ( q , a ) formata da uno stato e da un simbolo di input.
q Q cioè lo stato iniziale•
∈F Q cioè gli stati finali•
⊆Negli automi a stati finiti non deterministici un arco può essere etichettato con la ε e tali archi possono essere attraversati silenziosamente senza consumare nessun simbolo di input.
Un NFA N = < Σ , Q , δ , q , F > accetta la stringa x = a1…an se nel digramma di transizione esiste un cammino che inizia in q e termina in uno stato di F nel quale la stringa che si ottiene concatenando le etichette degli archi percorsi è esattamente x
Automi a stati finiti deterministici
Un caso particolare di NFA si ha quando non vi sono archi
etichettati con ε e inoltre nella funzione di transizione si ha che δ(q, a) è sempre un singoletto cioè che contiene esattamente un solo stato. In tal caso si ha un automa a stati finiti deterministico. Un automa finito deterministico (DFA) è una quintupla: <Σ, Q, δ, q, F> che differisce da un NFA per la funzione di transizione che è δ: Q x Σ -> Q. Si noti che da uno stato di un DFA deve uscire esattamente una transizione per ciascun simbolo dell'alfabeto. Quindi, dato un input x, un DFA ha uno ed un solo cammino etichettato x uscente dallo stato iniziale e che porterà il DFA nello stato finale se x appartiene al linguaggio accettato dall'automa. DFA e NFA sono equivalenti. Si può dimostrare che da un qualsiasi NFA N si può costruire un DFA M tale che |L(N)| = |L(M)|. Viceversa è un ovvietà in quanto il DFA è un caso particolare di NFA.prima cosa bisogna dire che in un NFA ci sono due cause di non determinismo ed esse sono la presenza di ε-transizioni che vengono eseguite senza consumare input e la possibilità che da uno stato partano più transazioni con la stessa etichetta. Per trasformare un NFA in DFA equivalente, è utile poter indicare in modo sintetico gli stati raggiungibili a partire da uno stato fissato esplicitandone le scelte deterministiche. ε-closure La ε chiusura di uno stato q è l’insieme degli stati che si possono raggiungere da q tramite ε-transizioni. Essa si usa per gestire la forma di indeterminismo delle ε-transizioni. Fissato un NFA N = < Σ , Q , δ , q , F > ed uno stato q ∈ Q, la ε-chiusura di q, indicata con εClosure(q), è l'insieme di tutti gli stati raggiungibili da q tramite ε-transizioni.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo
