Informatica teorica: sintesi

Sintesi degli argomenti del corso di Informatica Teorica

Periodo: 03/10/2016 – 16/12/2016

Corso di Laurea: Informatica

Principali argomenti di informatica teorica

• Chiusura linguaggi regolari e context-free (dimostrazione)
• Quintupla di A e A complemento
• Dato il linguaggio { (aⁿ b)* | con n pari } scrivere l'automa e complemento
• Che vuol dire automa minimo? (definizione)
• Che vuol dire che due stati sono indistinguibili?
• L'automa minimale è unico?
• I problemi P e NP? (spiegazione)
• Che vuol dire tempo polinomiale?
• Scrivere la grammatica delle stringhe palindrome
• Scrivere la grammatica delle parentesi
• CNF e trasformazione di una grammatica
• Lemma di iterazione (P. Lemma 2, dimostrazione)
• Verifichiamo se due automi riconoscono lo stesso linguaggio?
• Automa minimo unico? (dimostrazione per assurdo)
• Problemi: emptyness, inclusion (spiegazione e dimostrazione)
• Berry e Sethy (spiegazione algoritmo)
• Linguaggi locali (definizione e quadrupla)
• NFA e DFA hanno la stessa potenza? (dimostrazione con subset)
• Macchina di Turing
• Chi dice che la macchina di Turing riesce a calcolare tutte le funzioni? (Turing/Church)
• Descrizione e spiegazione della macchina (con settupla)
• Transizioni della macchina per fare la somma di due numeri

1. Chiusura dei linguaggi regolari

I linguaggi regolari sono chiusi per:

• Unione
• Intersezione
• Complemento

1.1 Chiusura per intersezione

Teorema: Se L₁ e L₂ REC, allora L₁ ∩ L₂ REC.

Dimostrazione per costruzione: Si costruisce un automa che riconosce l'intersezione dei due linguaggi: siano A₁ e A₂ due automi, anche incompleti, che riconoscono rispettivamente i linguaggi L₁ ed L₂ (L₁=L(A₁), L₂=L(A₂)).

A₁ = (Q,Σ,δ,q₀,F) A₂ = (Q,Σ,δ,q₀,F).

Si costruisce l'automa per intersezione A = (Q,Σ,δ,q₀,F) dove Q = {(q₁,q₂)|q₁ ∈ Q₁ AND q₂ ∈ Q₂} cioè Q = Q₁ x Q₂, q₀ = (q₀,q₀), δ = ((q₁,q₂),a) = (δ(q₁,a),δ(q₂,a)) ∀ a ∈ Σ.

F = {(q₁,q₂)|q₁ ∈ F₁ AND q₂ ∈ F₂} cioè F = F₁ x F₂.

È semplice provare che A riconosce L₁ ∩ L₂.

1.2 Chiusura per complemento

Teorema: se L REC, L^c REC.

Dimostrazione per costruzione: Si costruisce un automa che riconosce il complemento L^c = Σ* - L. Dato A = (Q,Σ,δ,q₀,F) che riconosce L, si costruisce A^c = (Q,Σ,δ,q₀,F^c).

Si completa l'automa, quindi bisogna sempre dichiarare l'alfabeto rispetto al quale si vuol fare la costruzione. Gli stati di accettazione diventano di non accettazione e viceversa. A^c riconosce L^c.

1.3 Chiusura per unione

Teorema: se L₁ e L₂ REC, allora (L₁ U L₂) REC.

Ci sono due modi per dimostrarlo:

• Tramite la legge di Morgan: L₁^c ∩ L₂^c = (L₁ U L₂)^c
• Per costruzione: siano A₁ e A₂ due automi che riconoscono rispettivamente i linguaggi L₁ e L₂, ipotizzati completi.

A₁ = (Q,Σ,δ,q₀,F) A₂ = (Q,Σ,δ,q₀,F).

Si costruisce l'automa unione A = (Q,Σ,δ,q₀,F) dove Q = {(q₁,q₂)|q₁ ∈ Q₁ AND q₂ ∈ Q₂}, q₀ = (q₀,q₀), δ = ((q₁,q₂),a) = (δ(q₁,a),δ(q₂,a)) ∀ a ∈ Σ, F = {(q₁,q₂)|q₁ ∈ F₁ OR q₂ ∈ F₂}.

Si può provare che A riconosce (L₁ U L₂), facendo l'unione tramite l'ε-transizioni.

2. Chiusura dei linguaggi context-free

Linguaggi liberi dal contesto

2.1 Chiusura per unione

Siano <Σ₁,V₁,S₁,P₁> e <Σ₂,V₂,S₂,P₂> due linguaggi non contestuali, la loro unione diventa: <Σ₁ U Σ₂, V₁ U V₂ U {S'}, S', P₁ U P₂> dove S' → S₁ U S₂ è il nuovo assioma.

2.2 Chiusura per concatenazione

Avendo <Σ₁ U Σ₂, V₁ U V₂ U {S'}, S', P₁ U P₂>, aggiungiamo la regola di produzione S' → S₁ U S₂ ed S' è il nuovo assioma.

2.3 Chiusura per iterazione

Dato <Σ₁,V₁,S₁,P₁>, si ha <Σ₁,V₁ U {S'},S',P₁> aggiungendo S' → S₁ S'|ε e usando S' come nuovo assioma.

2.4 Chiusura per intersezione

L'intersezione di due linguaggi c.f. non è necessariamente c.f.

Es. {aⁿ bⁿ c^m | n ≥ 1} ∩ {aⁿ b^m cⁿ | n ≥ 1} non è context free perché viene aⁿ bⁿ cⁿ che non è cf.

2.5 Chiusura per complemento

La chiusura per complemento non è necessariamente context free e lo si dimostra con De Morgan (L₁^c U L₂^c) = L₁ ∩ L₂ e l'intersezione non è necessariamente context free.

3. DFA e automa minimale

Un DFA (quintupla Q,Σ,δ,q₀,F) è un automa a stati finiti deterministico che, dopo aver letto una sequenza in input, si ferma in un singolo stato. Esso è composto da 5 componenti:

• Q: insieme degli stati;
• Σ: insieme dei caratteri di input;
• δ(q,a): funzione di transizione;
• q₀: stato iniziale;
• F: stato finale o di accettazione che è incluso in Q; possono esistere più stati finali.

Tra tutti gli automi equivalenti, l'automa minimale è quello con il minor numero di stati:

• per i DFA il minimale è unico;
• per gli NFA il minimale non è unico.

Minimizzare un automa significa trovare il minimale equivalente. Esistono vari algoritmi di minimizzazione:

• Algoritmo di Moore O(n²)
• Algoritmo di Hopcroft O(n log n)
• Algoritmo di Brzozowski (tempo esponenziale)
• dove n = numero di stati dell'automa da minimizzare

4. Relazione di indistinguibilità

La relazione di indistinguibilità è una relazione tra gli stati di un automa.

Sia A = (Q,Σ,δ,q₀,F) un DFA e {p,q} ⊆ Q.

Allora, pIq <=> ∀w ∈ Σ* | δ*(p,w) ∈ F <=> δ(q,w) ∈ F.

Invece, p e q sono distinguibili se:

∃w ∈ Σ* | δ*(p,w) ∈ F AND δ*(q,w) ∉ F o viceversa.

La relazione di indistinguibilità è una relazione di equivalenza:

• Proprietà riflessiva: pIp ∀p ∈ Q
• Proprietà simmetrica: pIq → qIp ∀p,q ∈ Q
• Proprietà transitiva: pIq, qIr → pIr ∀p,q,r ∈ Q

Ogni stato del minimale è una classe della partizione e quindi si devono trovare le classi di stati indistinguibili.

4.1 Teorema di Nerode

Sia A = (Q,Σ,δ,q₀,F) un automa che riconosca L. π = {Q₁,Q₂,...,Q_m} la partizione di indistinguibilità.

L'automa minimo che riconosce L è MA = (Q_M,Σ ,δ_M,q₀,F_M) dove

• Q_M = {Q₁,Q₂,...,Q_m}
• q₀ = [q₀]
• δ_M ([q],a) = [δ(q,a)], ∀q ∈ Q AND ∀a ∈ Σ
• F_M = { [q] | q ∈ F}

Affinché la funzione di transizione sia ben definita, si deve mostrare che applicando δ a qualunque stato di una classe si arriva alla stessa classe:

Se pIq, allora δ(p,a)Iδ(q,a)

5. Grammatica generatrice di palindrome e parentesi

L = Linguaggio delle palindrome

G = Grammatica che genera L

G = <{S},{a,b},S,P> dove P sono le seguenti regole di produzione:

• S → aSa
• S → bSb
• S → a
• S → b
• S → aa
• S → bb

L = Linguaggio delle parentesi

G = Grammatica che genera L

G = <{S},{ '(', ')' },S,P>