CIS 262 lingue - CIS 262 - UPENN

Introduzione alla Teoria della Computazione

Jean GallierDepartment di Computer e Informazioni ScienceUniversity di PennsylvaniaPhiladelphia, PA 19104, USAe-mail:[email protected]

©c Jean GallierPlease, fare notreproducewithout il permesso dell’autore

Marzo 5, 2020

4 CONTENUTI

6.4 Il Pompaggio Lemma
6.5 Un Algoritmo Veloce per Controllare lo Stato di Equivalenza
7 Contesto di Grammatiche E Linguaggi
7.1 Context-Free Grammars
7.2 e Derivazioni Contesto di Lingue
7.3 Forme Normali per il Contesto-Free Grammars
7.4 Linguaggi Regolari sono Libera dal Contesto,
7.5 Inutile Produzioni in Contesto di Grammatiche
7,6 Greibach Forma Normale
7.7 Meno Fissa Punti
7.8 Contesto di Lingue come Minimo Fisso di Punti
7.9 Meno Fissa Punti e il Greibach Forma Normale
7.10 Albero Domini e Gorn Alberi
7.11 Derivazioni Alberi
7.12 Ogden, Lemma
7.13 Pushdown Automi
7.14 Dal Contesto di Grammatiche Per PDA
7.15 Da PDA A Context-Free Grammars
7.16 La Chomsky-Schutzenberger Teorema
8 Un Sondaggio ofLR-Metodi di Analisi
8.1 LR(0)-Caratteristica Automi
8.2 Shift/Reduce Parser
8.3 Calcolo di PRIMA
8.4 L’Intuizione alla base della Shift/Reduce Algoritmo
8.5 Il Metodo Grafico per il Calcolo dei Punti Fissi
8.6 Calcolo di SEGUIRE
8.7 AlgorithmTraverse
8.8 Più onLR (0)-Automi caratteristici
8.9 LALR (1) – Set di Lookahead
8.10 Calcolare PRIMA, SEGUIRE, ecc. in presenza diǫ-Rules
8.11 LR(1)-Characteristic Automata

Introduzione

La teoria del calcolo riguarda gli algoritmi e i sistemi algoritmici: la loro progettazione e rappresentazione, la loro completezza e complessità.

Lo scopo di queste note è quello di introdurre alcune delle nozioni di base della teoria ofcomputation, tra cui concetti da linguaggi formali e la teoria degli automi, la teoria ofcomputability, alcune nozioni di base della teoria delle funzioni ricorsive, e un’introduzione a complexitytheory. Altri argomenti come la correttezza dei programmi non saranno trattati qui (non c’è abbastanza tempo!).

Le note sono divise in tre parti. La prima parte è dedicata alingue formalie automi. La seconda parte riguarda modelli di calcolo, funzioni ricorsive e indecidibilità. La terza parte riguarda la complessità computazionale, inparticolare la classesPandNP.

5

Nozioni di base sulla teoria del linguaggio formale

2.1 Revisione di alcune notazioni matematiche di base e

N,Z,Q,R,C.

I numeri naturali, N={ 0 , 1 , 2 ,…}.

Theintegers, Z = {…,− 2 ,− 1 , 0 , 1 , 2 ,…}.

I risultati,

{

|p, q Z Z, q 6 = 0

}

null

Thereals, R. Thecomplex numbers, C = {a + ib / a, b R R}.

Dato qualsiasi setX, ilpotenza SET dixè l’insieme di tutti i sottoinsiemi dixe è denotato 2X.La notazione f:X→Y

denota una funzione con dominoxandrange(orcodomain)Y.

graph(f) ={(x,f(x)}|x} X}} X×Y

è il grafico.

7 8 CAPITOLO 2. LA TEORIA DEL LINGUAGGIO FORMALE

Im (f) =f (X)={y |Y / x x X X, y = f(x)} Y Y

è l’imageoff.

Più in generale, if X X, quindi

f(A) ={y |Y / / x / A, y=f(x)} Y Y

è l’immagine(diretta) di A.

IfB Y Y, quindi f – 1 (B) = {x x X|f(x)} B} X X

è l’immagine inversa(o il retro) DiB.

f− 1 (B) è un insieme; potrebbe essere vuoto anche ifB 6 =∅.Date due funzionif: X→Y eg: Y→Z, la funzioneg◦f: X→Zdata da

(g◦f)(x) =g(f(x)) per tuttix X X

è la composizione offandg.

La funzione idX:X→Xdata da

idX(x) =x per allx X X

è la funzione identity(ofX).

Una funzionef: X→Y èiniettivo (vecchia terminologiauno a uno)se per allx 1 ,x 2 X X,

iff (x 1) =f (x 2), thenx 1 = x 2 ;

equivalente ifx 16 = x 2, thenf(x 1 ) 6 =f (x 2 ).

Fatto: IfX 6 =∅(e soY 6 =∅), una functionf:X →Y è iniettiva se c’è una functionr:Y →X (aleft inverso) tale che

r◦f= idX.

Nota:soggettiva.A functionf:X→Y issurjective(old terminologyonto)se per ally ally Y, c’è somex that Xsuch thaty=f(x), ifff(X) =Y.

Fatto: IfX 6 =∅(e soY 6 =∅), una functionf:X→Y è surjective se c’è una functions:Y →X(right inverseorsection) tale che

f◦s= idY.

10 CAPITOLO 2. NOZIONI di base DI TEORIA dei linguaggi FORMALI

UN relationR⊆X×Xissymmetricif per allx,y∈X, se (x,y)∈R, allora (y,x)∈R

Un relationR⊆X×Xis simmetrica iffR− 1 ⊆R.

GivenR⊆X×X(una relazione onX), defineRnby

R 0 =IXRn+1=R◦Rn.

Il Closurer transitivo + OFRIS dato da

R+=

⋃

n≥ 1

Rn.

Fatto.R + è la più piccola relazione transitiva contenenteR.

Closurer flessibile e transitivo given OFRIS dato da

R∗=

⋃

n≥ 0

Rn=R+IX IX.

Fatto.R∗è la più piccola relazione transitiva e riflessiva contenenteR.

Una relazioner×X × Xè una relazione di anequivalenza se è riflessiva, simmetrica e transitiva.

Fatto. La più piccola relazione di equivalenza contenente una relazioner×X × Xè dato da

(R R R− 1 )∗.

Una relazioner×X×Xisantisimmetricif per allx,y X X, if (x,y) R Rand (y,x) R R,thenx=y.

Una relazioner order X × X è un ordine parziale se è riflessivo, transitivo e antisimmetico.

Un ordine partialr×X × X è un ordine totale se per allx,y X X, o (x,y) R Ror(y,x) R R.

2.2 Alfabeti, stringhe, lingue

La nostra visione delle lingue è cheuna lingua è un insieme di stringhe. A sua volta, una stringa è una finitasequenza di lettere da qualche alfabeto. Questi concetti sono definiti rigorosamente come segue.

Definizione 2.1.AnalphabetΣ è anyfiniteset.

2.2. ALFABETI, STRINGHE, LINGUE 11

Scriviamo spesso Σ ={a 1 ,…, ak}. Ilai sono chiamati i simboli dell’alfabeto.Esempio:Σ = {a} Σ = {a,b , c}Σ ={ 0,1 }Σ ={α,β,γ,δ,λ,λ,φ,ψ,ω,μ,ν,ρ,σ,η,ξ, ζ}Una stringa è una sequenza finita di simboli. Tecnicamente, è conveniente definire stringhe comefunzioni. Per qualsiasi integern≥1, lasciare

={ 1 , 2 ,…, n},

e forn = 0, let =∅.

Definizione 2.2. Dato un alfabeto Σ, astring overΣ (o semplicemente una stringa) di lunghezza nisany funzione

u: →Σ.

L’integern è la lunghezza dello stringu, ed è indicato come|u|. Whenn= 0, thespecial stringu: →Σ di lunghezza 0 è chiamato theempty string, o null string, ed è denotato comeǫ.

Dato uno stringu: →Σ di lengthn≥1,u(i) è la lettera nella stringu. Per la semplicità della notazione,scriviamo uiinvece di u(i), e denotiamo lo stringu=u(1)u(2)···u(n)come

u=u 1 u 2 ···un,

con ciascunui Σ Σ.

Ad esempio,se Σ ={a,b}andu: →Σ è definito tale cheu(1) =a, u(2) =b, andu(3) =a, scriviamoeu=aba.

Altri esempi di stringhe sono

work, fun, gabuzomeuh

Le stringhe di lunghezza 1 sono functionsu: →Σ semplicemente raccogliendo alcuni elementu(1) =aiin Σ.Quindi, identificheremo ogni symbolai Σ Σ con la stringa corrispondente di lunghezza 1.

L’insieme di tutte le stringhe su un alfabeto Σ, inclusa la stringa vuota,è indicato come Σ∗.

2.2. ALFABETI, STRINGHE, LINGUE 13

Per la base casen= 0, sinceu 0 =ǫ, abbiamo

u 0 u = uchu = u=uǫ = uu 0.

Per la fase di induzione, abbiamo

un+1u= (unu)u per definizione ofun+ = (uun)u per ipotesi di induzione =u(unu) per associatività =uun+1 per definizione ofun+1.

Definizione 2.4.Dato un alfabeto Σ, dato qualsiasi due stringsu, v Σ Σ define definiamo le seguenti note come segue:

uis un prefisso di viff c’è un po ‘ Σ Σ such tale che

v=uy.

uis un suffisso ofviff c’è somex Σ Σ such tale che

v=xu.

uis una sottostringa ofviff ci sono somex,y Σ Σ such tale che

v=xuy.

Diciamo cheuè un prefisso (suffisso, sottostringa) diviffuè un prefisso (suffisso, sottostringa)divandu 6 =v.

Ad esempio,gaè un prefisso digabuzo,zois un suffisso digabuzoebuzè una sottostringa digabuzo.Ricordiamo che un ordinamento parziale≤ su un SET è una relazione binaria≤ S S×S che isreflexive, transitive e antisimmetriche.

I concetti di prefisso, suffisso e sottostringa definiscono le relazioni binarie su Σ∗in modo ovvio. Si può dimostrare che queste relazioni sono ordini parziali.

Un altro importante ordinamento sulle stringhe è l’ordinamento lessicografico (o dizionario).

Definizione 2.5. Dato un alfabeto Σ ={a 1 ,…,ak}assunto totalmente ordinato in modo thata 1 < un 2 <···< ak, dati due stringsu,v∈Σ∗, definiamo thelexicographic orderingas segue:







(1) ifv=uy, per somey∈Σ∗, o(2) ifu=xaiy,v=xajz,ai< aj,withai,aj∈Σ, e per somex,y,z∈Σ∗.

14 CAPITOLO 2. NOZIONI DI BASE DELLA TEORIA DEL LINGUAGGIO FORMALE

L’idea è che scanuandvsimultaneously da sinistra a destra, confrontandoli thsymboluminuto themth symbolvminv, a partire dam= 1. Se non si verifica alcuna discrepanza, quelloè, se loro-esimo simbolouminuagreeswith them-esimo simbolovminvform= 1,…,| u/, iluè un prefisso div e lo dichiariamo senza precedenti nell’ordinamento lessicografico. Altrimenti, per un po ‘ euandvagree lungo un prefisso comunex(possibilmente la stringa vuota), e poic’è aleftmost discrepanza, il che significa cheuis del formu=xaiyandvis delformv=xajz,conai 6 =aj(andx,y, z Σ Σ arbitrary arbitrario). Quindi abbiamo bisogno di rompere il legame, eper fare questo usiamo il fatto che i simboliun 1 < a 2 <···< si presume che ak sia (totalmente)ordinato, quindi vediamo quale ofaiandajcomes per primo, sayai< aj, e dichiariamo cheu=xaiyprecedesv=xajzin l’ordine lessicografico.

Si noti che i casi (1) e (2) si escludono a vicenda. Nel caso (1), uis un prefisso ofv. Nel caso(2)v6uandu 6 =v.

Ad esempio abb, gallhagergallier.

È abbastanza noioso dimostrare che l’ordinamento lessicografico è in realtà un ordinamento parziale.In effetti, è un ordinamento totale,il che significa che per qualsiasi due stringsu, v Σ Σ∗, oitheruv, orvu.

ilversalwrof a stringwis definito induttivamente come segue:

ǫR=ǫ,(ua)R=auR,

wherea and Σ andu Σ Σ∗.

Ad esempio reillag=gallierR.

Da settingu=ǫin (ua)R=auR,

sinceǫR=ǫanda=ǫa, otteniamo

aR= (ǫa)R=aǫR=aǫ=a,

namelyaR=afor alla∈Σ.

Può essere mostrato per induzione su / v / che

(uv)R=vRuR.

Un trucco utile che riduce la notazione ingombrante quando si fa l’induzione sulle stringhe è l’osservazione che anonempty stringw Σ Σ of di lunghezzan+ 1 (n≥0) può essere scritto come

w=ua, per someu some Σ∗e alcuni symbola Σ Σ, con|u|=n.

16 CAPITOLO 2. NOZIONI DI BASE DELLA TEORIA DEL LINGUAGGIO FORMALE

SEX non è l’insieme vuoto, da alloraf:X→Nè un’iniezione se c’è una suriezione r:N→Xtale che r◦f= idX, l’setxè numerabile se c’è unriezione Danontox.

Fatto. Si può dimostrare che un setxè numerabile se è finito o se è in bijectionwithN (nel qual caso è infinito).

Vedremo più avanti thatN×Nis numerabile. Di conseguenza, il SETQ di numeri razionali è numerabile.

Un set isuncountableif non è numerabile.

Ad esempio,R(l’insieme di numeri reali) non è numerabile.Allo stesso modo

(0,1) ={x R R / 0 < x < 1 }

non è numerabile. Tuttavia, c’è una bijection tra(0,1) andR (trova uno!) L’insieme 2Ndi tutti i sottoinsiemi diNis non numerabile. Questo è un caso speciale del teorema di cantordiscusso di seguito.

Supponiamo|Σ|=kwith Σ ={a 1 ,…, ak}. Innanzitutto, osserva che ci sonostringhe di lunghezzae(kn+1-1)/(k−1) stringhe di lunghezza al massimonover Σ; quandok= 1, la seconda formuladovrebbe essere sostituita da n+ 1. Infatti, poiché una stringa è una functionu: {1,…, n} →Σ, il numero di stringhe di lunghezzaè il numero di funzioni da{ 1,…, n}a Σ, e poiché la cardinalità di Σ isk, ci sonotali funzioni (questo è immediatamente mostrato dall’induzione onn). Quindi il numero di stringhe di lunghezza al massimoè

1 + k + k 2 +···+nn.

Se k = 1, questo numero è n+ 1, e se k ≥ 2, come somma di una serie geometrica, è (kn+1-1) / (k−1).

Se Σ 6 =∅, allora l’insieme Σ∗di tutte le stringhe su Σ è infinito e numerabile, come mostriamocostruendo una biiezione esplicita da Σ on ontoN.

Ifk = 1 writea=a 1, e poi

{a}= = {ǫ, a, aa, aaa,…,un,…}.

Abbiamo la bijectionn7→anfromNto{a}∗.Ifk≥2, allora possiamo pensare alla stringa

u=ai 1 ···ain

come una rappresentazione dell’integerv(u) in basekshifted da (kn−1)/(k−1), con

2.2. ALFABETI, STRINGHE, LINGUE 17

ν (u) =i 1 kn-1 + i 2 kn− 2 +···+in-1 k + in

kn-1 k− 1

(i 1 -1)kn− 1 +···+ (in− 1 -1)k + in-1.

(e con v (ǫ) = 0), dove 1≤ij≤kforj= 1,…, n.

Lo lasciamo come esercizio per mostrare chev: Σ→ → N è una biiezione. Findingexplitly (thatis, una formula) per l’inverso divis sorprendentemente difficile.

Infatti,ν corrisponde all’enumerazione di Σ where dove uprecedesv if|u| < |v|, e uprecedesv nell’ordinamento lessicografico if|u|=|v|. È facile verificare che aboverelation (uprecedesv) sia un ordine totale.

Per esempio, l’ifk= 2 e se scriviamo Σ ={a,b}, allora il conteggio inizia con

denita come,0a, b,1 , 2 ,aa, ab, ba, bb,3 , 4 , 5 , 6 ,aaa, aab, aba, abb, baa, bab, bba, bbb7 , 8 , 9 , 10 , 11 , 12 , 13 , 14

Per ottenere la riga successiva, concatenateaon sinistra, e poi concatenatebon sinistra. Wehavev (bab) = 2· 22 + 1· 21 + 2 = 8 + 2 + 2 = 12.

Funziona!

D’altra parte, se Σ 6=∅, l’insieme 2Σ ∗ di tutti i sottoinsiemi di Σ∗(tutte le lingue) non è numerabile.In effetti, possiamo dimostrare che non c’è suriezione da 2Σ ∗ In primo luogo, mostreremo chenon c’è suriezione da Σ∗su 2Σ∗. Questo è un caso speciale del teorema di Cantor.Sosteniamo che se non c’è suriezione da Σ∗su 2Σ ∗ , allora non c’è suriezione da 2Σ either.

Prova. Supponiamo per contraddizione che ci sia una suriezione g: N→ 2 Σ ∗ . Ma, se Σ 6=∅, thenΣ∗è infinito e numerabile, quindi abbiamo la bijectionv: Σ→ → N. Quindi la composizione

σ ν ν // N

g // 2 Σ

è una suriezione, perché la bijectionvis una suriezione,gis una suriezione, e la composizionedi suriezioni è una suriezione, contraddicendo l’ipotesi chenon c’è suriezione daσ onto su 2Σ∗.

2.3. OPERAZIONI SULLE LINGUE 19

2.3 Operazioni sulle lingue

Un modo per costruire linguaggi più complessi da quelli più semplici è combinarli usandovarie operazioni. Innanzitutto, esaminiamo le operazioni teoriche dell’insieme di unione, intersezione ecomplementazione.

Dato qualche alfabeto Σ, per due languagesL 1 ,L 2 Σ, theunionL 1 ∪L 2 ofL 1andL 2 è la lingua

L 1 ∪L 2 ={w∈Σ∗|w∈L 1 o w∈L 2 }.

TheintersectionL 1 ∩L 2 ofL 1 el 2 è la lingua

L 1 ∩L 2 ={w∈Σ∗|w∈L 1 e w∈L 2 }.

Ildifferencel 1-L 2 ofL 1 e L 2 è la lingua

L 1-L 2 ={w Σ Σ Σ / w L L 1 e w / L L 2 }.

La differenza è anche chiamata ilcompleto relativo.

Un caso speciale della differenza si ottiene quando L 1 = Σ∗, nel qual caso definiamo ilcomplementl di una linguacome

L={w w Σ}|w /L L}.

Le operazioni di cui sopra non utilizzano la struttura delle stringhe. Le seguenti operazioni usanoconcatenazione.

Definizione 2.8.Dato un alfabeto Σ, per due languagesL 1 ,L 2 Σ, theconcatenationL 1 L 2 ofL 1 el 2 è la lingua

L 1 L 2 ={w∈Σ∗|∃u∈L 1 ,∃v∈L 2 , w=uv}.

Per qualsiasi languageL, definiamo come segue:

L 0 ={}}, Ln+1=LnL (n≥0).

settingn= 0 inLn+1=LnL, sinceL 0 = {}}, otteniamo

L 1 = L0+1 = L 0 L = {}} L = L,

soL 1 =L.

20 CAPITOLO 2. NOZIONI di base DI TEORIA dei linguaggi FORMALI

Le seguenti proprietà sono facilmente verificabili:

L∅=∅,∅L=∅,L{denita come}=L{denita come}L=L,(L 1 ∪{denita come})L 2 =L 1 L 2 ∪L 2 L 1 L 2 ∪{denita come}) =L 1 L 2 ∪L 1 ,LnL=LLn.

In generale, L 1 L 26 =L 2 L 1.So lontano, le operazioni che abbiamo introdotto, tranne la complementazione (sinceL= Σ∗−Lis infinito ifLis finito e Σ è non vuoto), preservano la finitezza delle lingue. Questo non èil caso per le prossime due operazioni.

Definizione 2.9.Dato un alfabeto Σ, per qualsiasi linguasopra Σ, ilcleene clos-closureL of ofLis la lingua

L L=