Richiami e complementi su linguaggi formali



Scaricare 113.22 Kb.
22.05.2018
Dimensione del file113.22 Kb.


PARTE I


RICHIAMI E COMPLEMENTI SU

LINGUAGGI FORMALI

E AUTOMI

Linguaggi regolari, linguaggi

non contestuali e automi
Macchine di Turing multinastro e

non deterministiche
Macchine di Turing e

linguaggi di tipo 0 e di tipo 1

1.1 I LINGUAGGI IN INFORMATICA

@ Presenti in tutte le applicazioni


linguaggi di programmazione

linguaggi di marcatura

protocolli

sequenze di operazioni

interazione uomo macchina
@ Fondamentali nel software di sistema
compilatori

interpreti

generatori di analizzatori
@ Paradigmatici nella teoria
molti importanti problemi teorici sono riconducibili a quello dell'appartenenza di una stringa a un linguaggio

Metodi di descrizione di linguaggi
Approccio generativo: un linguaggio può essere definito mediante regole (metalinguaggi) che specificano la struttura sintattica delle sue stringhe.
Esempi

Grammatiche di Chomsky

Forma di Backus Naur (BNF)

Linguaggi di tag (HTML, XML)


Approccio riconoscitivo: un linguaggio può essere definito mediante macchine astratte (automi) o algoritmi che accettano le stringhe che ne fanno parte e rifiutano quelle che non ne fanno parte.
Esempi

Automi a stati finiti

Automi a pila
Approccio algebrico: un linguaggio può essere definito mediante una espressione algebrica che specifica come esso è costruito a partire da linguaggi elementari.
Esempio

Espressioni regolari


ESPRESSIONI REGOLARI
Def. Dato un alfabeto , chiamiamo espressione regolare una stringa r sull'alfabeto

({+,*,(,),.,Ø})

tale che:

1. r = Ø oppure

2. r  oppure

3. r= (s+t) oppure r= (s.t) oppure r=s*,

con s e t espressioni regolari
espressione linguaggio

Ø 


a {a} a 

(s+t) L(s) L(t) s, t e.r.

(s.t) L(s) ° L(t)

s* L(s)*

Per semplificare la scrittura delle espressioni regolari possiamo sfruttare:
• eliminazione del simbolo della concatenazione, cioe' (st) anziche' (s.t)

• precedenze tra operatori: * > . > +


Esempi.
(a+(b.(c.d))) = a+bcd
(a+b)* rappresenta L=({a}{b})*
(a+b)*a rappresenta il linguaggio

L={x| x {a,b}*  "x termina con a"}



1.2 GRAMMATICHE FORMALI

Metodo di costruzione delle stringhe del linguaggio basato sulla riscrittura


1914 Axel Thue studia i primi problemi di riscrittura.
1943 Emil Post definisce sistemi di produzione (lavori del 1920).
1947 A.A. Markov definisce algoritmi basati su regole di riscrittura.
1956 N. Chomsky introduce le grammatiche formali nell'ambito degli studi sul linguaggio naturale.
1960 J. W. Backus e P. Naur introducono la BNF per descrivere la sintassi del linguaggio Algol.

Le Grammatiche di Chomsky


Def. Una grammatica formale e' un sistema G = T,VN,P,S>

caratterizzato da:


• VT (alfabeto finito di simboli detti terminali,
• VN alfabeto di simboli

non terminali

(variabili, categorie sintattiche),
• P, detto insieme di produzioni, e' una relazione binaria finita su

(VTVN)*°VN°(VTVN)*  (VTVN)*



<,> P si indica con 
• S VN e' detto assioma.
Def. Il linguaggio generato da una grammatica e' l'insieme delle stringhe di terminali ottenibili con una sequenza finita di passi di riscrittura consistenti nell'applicazione delle regole di produzione

Più formalmente:



Def. Derivazione diretta: relazione su

(V*°VN°V*)  V*



<,> appartiene alla relazione

se V*°VN°V* e V*

tali che =  =  e P

In tal caso si scrive .


Def. Derivazione: chiusura riflessiva e transitiva della derivazione diretta, si rappresenta con *.
Def. Data una grammatica

G = <{a,b},{S,B,C},P,S>, una

forma di frase e' una qualunque stringa x tale che xV*e S*x.
Il linguaggio generato da G e' l'insieme di particolari forme di frase:
Def. Il linguaggio generato da G e'

L(G) = {x | xVT* S*x}


Def. Due grammatiche G1 e G2 si dicono equivalenti se L(G1) = L(G2).

Esempio. G=<{a,b,c},{S,A,B,C},P,S>
1 S  aSBC

2 S  aBC

3 CB  BC

4 aB  ab

5 bB  bb

6 bC  bc

7 cC  cc

genera il linguaggio {anbncn | n≥1}


Per generare 'aaabbbccc' si effettua la seguente derivazione (la stringa che viene riscritta e' sottolineata, il numero rappresenta la produzione applicata):
S (1)  aSBC

(1)  aaSBCBC

(2)  aaaBCBCBC

(3)  aaaBCBBCC

(3)  aaaBBCBCC

(3)  aaaBBBCCC

(4)  aaabBBCCC

(5)  aaabbBCCC

(5)  aaabbbCCC

(6)  aaabbbcCC

(7)  aaabbbccC

(7)  aaabbbccc



1.3 CLASSI DI GRAMMATICHE DI CHOMSKY E CLASSI DI LINGUAGGI

• di tipo 0, non limitate

• di tipo 1, contestuali (context sensitive: CS)

• di tipo 2, non contestuali (context free: CF),

• di tipo 3, regolari

Def. Le grammatiche di Chomsky di tipo 0, sono basate sulle produzioni piu' generali, del tipo:
 , V*°VN°V*, V*
NOTA BENE. Le grammatiche di tipo 0 ammettono anche derivazioni che accorciano stringhe.
Def. I linguaggi di tipo 0 sono i linguaggi generati da grammatiche di tipo 0.


Def. Le grammatiche di Chomsky di tipo 1, (dette context sensitive o contestuali) sono basate su produzioni del tipo:
 , V*°VN°V*, V+

con ||≤||



Def. I linguaggi di tipo 1 (context sensitive o contestuali) sono i linguaggi generati da grammatiche di tipo 1.
Def. Le grammatiche di Chomsky di tipo 2, (dette context free o non contestuali) sono basate su produzioni del tipo:
A , AVN, V+
Def. I linguaggi di tipo 2 (context free o non contestuali) sono i linguaggi generati da grammatiche di tipo 2.
Esempio. Generazione di espressioni aritmetiche con la variabile i, assioma E
E  E+T | T

T  T*F | F

F  i | (E)
Da quale sequenza di produzioni e' generata la stringa di parentesi: i * (i + i) ?
Esempio. Grammatica delle parentesi ben bilanciate:
S  ()

S  SS


S  (S)

Perche' le grammatiche di tipo 1 sono chiamate contestuali e quelle di tipo 2 non contestuali?


Nell'originaria formulazione data da Chomsky le grammatiche di tipo 1 sono definite come quelle grammatiche le cui produzioni hanno la forma:

con = e =,

e conVN , V*, V+


Quindi, se ||  1 o || , la produzione esprime il fatto che il non terminale A viene rimpiazzato dalla stringa  solo se appare nel contesto delle stringhe e. Per tale motivo quelle produzioni (e le relative grammatiche) sono chiamate "contestuali".
Esempio. Le produzioni
aBab, bBbb, bCbc, cCcc
della grammatica per il linguaggio {anbncn | n≥1} sono contestuali secondo Chomsky.

Teorema. Le grammatiche di tipo 1 e le grammatiche contestuali secondo Chomsky consentono di generare la stessa classe di linguaggi.
Dim. i) Le produzioni contestuali di Chomsky sono di tipo 1.

ii) Le produzioni di tipo 1 possono essere facilmente trasformate in produzioni contestuali di Chomsky. (Esercizio)


Ad esempio la produzione CB BC puo' essere trasformata nella sequenza di produzioni (contestuali secondo Chomsky):
CB  CX

CX  BX


BX  BC
NOTA BENE. Le produzioni di tipo 2 corrispondono al caso particolare in cui sia 

che  sono stringhe vuote. Tali produzioni consentono dunque di rimpiazzare un nonterminale con una stringa di caratteri, indipendentemente dal contesto in cui esso si trova. Per tale motivo esse (e le relative grammatiche) si chiamano "non contestuali".



Def. Le grammatiche di Chomsky di tipo 3, (dette regolari) sono basate su produzioni del tipo:
AaB oppure Aa,
con A, BVN, aVT
Def. I linguaggi di tipo 3 (regolari) sono i linguaggi generati da grammatiche di tipo 3.
Esempio. Il linguaggio {anb | n≥0} e' di tipo 3 in quanto e' generato dalla grammatica con le produzioni:
S  aS

S  b


Le grammatiche di tipo 3 sono chiamate anche lineari destre (LD).
Le grammatiche di tipo 3 vengono chiamate lineari perche' nel lato destro di ogni produzione compare al piu' un solo non terminale (variabile); inoltre vengono chiamate lineari destre perche' il non terminale compare a destra del terminale.
Si possono anche definire grammatiche lineari sinistre (LS) con produzioni del tipo:
ABa oppure Aa,
con A, BVN, aVT
Esempio. Il linguaggio {anb | n≥0}

puo' essere anche generato da una grammatica lineare sinistra con le seguenti produzioni:


S  Tb | b

T  Ta | a


Teorema. Le classi di linguaggi generabili con grammatiche LD e LS coincidono.


Def. Un linguaggio e' strettamente di Tipo n se esiste una grammatica di tipo n che lo genera e non esiste nessuna grammatica di tipo m>n che lo genera.
Esempi. Il linguaggio {anbn | n≥1} e' generato da una grammatica di tipo 2 e non e' generabile con nessuna grammatica di tipo 3.

Il linguaggio {anbncn | n≥1} e' generato da una grammatica di tipo 1 e non e' generabile con nessuna grammatica di tipo 2 o di tipo 3.


NOTA BENE. La dimostrazione dei suddetti risultati e’ basati sui noti “pumping lemma”.

Per mostrare linguaggi strettamente di tipo 0 è necessario introdurre ulteriori concetti.



1.4 LINGUAGGI LINEARI
I linguaggi lineari sono quei linguaggi CF generati da grammatiche lineari, in cui, cioe', la parte destra di ogni produzione contiene al piu' un non terminale
Le grammatiche di tipo 3 sono lineari; come si e' detto, in particolare, lineari destre (LD).
Esempio. La grammatica seguente, che genera {ancbn | n≥0} e' lineare:
S  aSb | c
Si noti che tale linguaggio e' strettamente CF.

I linguaggi lineari sono un sottoinsieme di quelli strettamente CF (ad esempio il linguaggio delle parentesi ben bilanciate non è un linguaggio lineare) e un soprainsieme di quelli regolari.


NOTA BENE: Fondendo produzioni lineari destre e lineari sinistre si possono generare linguaggi non regolari.
1.5 RICONOSCIMENTO DI LINGUAGGI
Dato un linguaggio L, il problema del riconoscimento di L e' il problema decisionale seguente: data una stringa x, stabilire se essa appartiene ad L. Tale problema e' noto anche come problema dell'appartenenza

(o membership).


• I linguaggi di tipo 3 sono riconosciuti in tempo lineare da dispositivi con memoria costante (automi a stati finiti).
• I linguaggi di tipo 2 sono riconosciuti in tempo lineare da dispositivi nondeterministici dotati di una memoria gestita come una pila (automi a pila non deterministici).

• I linguaggi di tipo 1 sono riconosciuti da dispositivi nondeterministici con memoria che cresce linearmente con la lunghezza della stringa da esaminare (automi non deterministici lineari o "linear bounded automata").


• Per alcuni linguaggi strettamente di tipo 0 e' possibile che non esista un algoritmo di decisione ma esiste comunque un processo semidecisionale, in cui, se la stringa fa parte del linguaggio essa viene riconosciuta ma se non fa parte del linguaggio non e' detto che la computazione termini. I dispositivi che consentono di riconoscere o di attuare un procedimento di semidecisione per i linguaggi di tipo 0 sono le macchine di Turing. In generale non e' possibile stabilire un limite alle quantita' di risorsa tempo o memoria che si rende necessario per riconoscere un linguaggio di tipo 0.

1. 6 LINGUAGGI REGOLARI E AUTOMI A STATI FINITI

I linguaggi regolari:


• sono generabili con grammatiche di tipo 3
• coincidono con i linguaggi definibili con espressioni regolari
• coincidono con i linguaggi riconoscibili con automi a stati finiti

deterministici o non deterministici


AUTOMI A STATI FINITI (ASF)





Def. Automa a stati finiti (ASF):
A=<,K,,q0,F>
 = {1,...,n}

alfabeto di input


K = {q0,...,qn}

insieme finito non vuoto di stati


K  F

insieme di stati finali


q0K

stato iniziale


 : K    K

funzione di transizione, funzione totale che determina lo stato successivo


Def. Funzione di transizione estesa alle stringhe:
: K  *  K
(q,) = q

(q,ax) = ((q,a),x), con x* e a
Def. Linguaggio riconosciuto da un automa A:
L(A) = { x * | (q0,x) F}
Esempio. Dato il linguaggio {anb | n≥0} generato da S  aS | b, l'automa che lo riconosce e' l'automa

<{a,b}, {q0,q1,q2}, , q0, {q1}>
 a b

q0 q0 q1

q1 q2 q2

q2 q2 q2






1.7 LINGUAGGI NON CONTESTUALI ED AUTOMI A PILA

I linguaggi non contestuali (context free):


• sono generabili con grammatiche di tipo 2
• coincidono con i linguaggi riconoscibili con automi a pila

non deterministici.

Forme normali per i linguaggi non contestuali
Forma ridotta: grammatiche


  • prive di -produzioni,

  • prive di produzioni unitarie,

  • prive di produzioni che contengono simboli inutili (cioè

Forma normale di Chomsky: grammatiche

di tipo 2 le cui produzioni sono del tipo
C con CVN
o del tipo
a con a
Forma normale di Greibach: grammatiche di tipo 2 le cui produzioni sono del tipo
 a con a,  V*

I linguaggi non contestuali sono tutti e soli i linguaggi che vengono riconosciuti da un automa a pila non deterministico (o automa "push-down", PDA)


Def. Automa a pila non deterministico (PDA)
M=<,,Z0,Q,q0,F,>
 alfabeto di input

 alfabeto dei simboli della pila

Z0  simbolo di pila iniziale

Q insieme finito di stati

q0 Q stato iniziale

Q F insieme di stati finali

 : Q  ({})    P(Q  *)

funzione di transizione.


Se abbiamo una regola di transizione


(qi,a,A)={(qj,BA),(qh,)}
essa significa che se nello stato interno qi, leggiamo a sul nastro ed A e' il simbolo affiorante sulla pila, si realizzano, non deterministicamente, due transizioni; la prima sostituisce il simbolo affiorante sulla pila con la stringa di caratteri BA e si porta nel nuovo stato interno qj, la seconda sostituisce il simbolo affiorante sulla pila con la stringa vuota , in altre parole cancella A dalla pila, e si porta nel nuovo stato interno qh.
NOTA BENE. La testina sul nastro di ingresso puo' anche non spostarsi. Questa situazione e' espressa dicendo che la testina legge  sul nastro di ingresso.
Convenzione: se metto BA in pila, B e' il nuovo simbolo affiorante.

Esempio. Automa a pila M che riconosce anbn
M = <{a,b},{Z0,A0,A},Z0,{q0,q1,q2},q0,{q2},>
- il simbolo A serve a ricordare la presenza delle a
- nello stato q0 si memorizzano le a, nello stato q1 si confrontano le b con cio' che si e' memorizzato, lo stato q2 e' lo stato finale.
NOTA BENE. In questo caso l'automa ha un comportamento deterministico






Z0

A0

A




a

b

a

b

a

b

q0

A0

q0





AA0

q0



A0

q2



AA

q0



q1



q1










A0

q2






q1



q2




















Def. Configurazione di automa a pila: tripla

con qQ stato interno, x* stringa da leggere in input e * stringa attualmente in pila
relazione di transizione per automa a pila: relazione binaria sulle configurazioni |
|
se vale:
((x=ax'  =Z  '= (q,a,Z)) 

(x=x'  =Z  '= (q,,Z)))


computazione: chiusura transitiva e riflessiva di |, indicata con |*
Def. Linguaggio accettato dall'automa a pila:
due definizioni alternative
• accettazione per pila vuota: una stringa e' accettata da un automa a pila M se e solo se al termine della scansione della stringa la pila e' vuota
N(M) = {x|0,x,Z0>|*}
• accettazione per stato finale: una stringa e' accettata da un automa a pila M se e solo se al termine della scansione della stringa M si trova in uno stato finale
L(M) = {x|0,x,Z0>|*,qF,*}

NOTA BENE. Si puo' dimostrare che le due definizioni sono equivalenti.

Teorema. Se L(G) e' non contestuale esiste un automa a pila M tale che L(G)=N(M)
Dim.
Sia G=<,VN,P,S> tale che L(G) e supponiamo G in GNF. In questo caso il PDA ha un solo stato e i non terminali della grammatica possono essere usati come simboli di pila.
Costruiamo M=<,,Z0,Q,q0,F,>
=VN, Z0=S, Q={q}, q0=q, F=
Per ogni Aa con VN*

abbiamo che (q,a,A)


E’ semplice dimostrare per induzione sulla lunghezza della derivazione di una stringa che tale costruzione è corretta.


Esempio: il linguaggio { wwR | w  (a+b)+} e’ generabile con la seguente grammatica in forma di Greibach:
S  aSA | bSB | aA | bB

A  a


B  b
Ed è riconoscibile (per pila vuota) con il seguente automa a pila:




S

A

B




a

b

a

b

a

b

q

SA, q

-----


A, q

SB, q

-----


B, q

, q





, q








Condividi con i tuoi amici:


©astratto.info 2017
invia messaggio

    Pagina principale