Introduzione al corso e Automi

Elementi di Teoria della Computazione

Prof. C. De Felice

Lezione 0: Introduzione al corso

3 Aree Centrali della Teoria della C.

• Teoria degli Automi
• Teoria della Calcolabilità
• Teoria della Complessità

La domanda, però, rimane la stessa:

Quali sono le capacità e i limiti dei computer

Teoria degli Automi

Lo scopo della teoria degli automi è studiare definizioni e proprietà dei modelli di computazione.

I modelli di computazione vengono classificati in base a restrizioni sulle risorse di memoria.

La caratteristica comune di tali modelli è che possono trovarsi in un numero finito di stati.

Essi dispongono di risorse di memoria differenti e quindi di potere computazionale diverso.

Il modello più semplice è l’automa a stati finiti, l’altro la macchina di Turing.

Questi modelli sono considerati come riconoscitori di linguaggi, piuttosto che come macchine che dato un input producono un output.

Teoria della Calcolabilità

La teoria della calcolabilità studia quali problemi possono essere risolti con un calcolatore.

Trovare una soluzione algoritmica per un problema può essere arduo, in molti casi è impossibile.

Le domande che si pone sono:

1. Quali sono i problemi risolvibili mediante una procedura effettiva?
2. Esistono problemi insolubili?

Godel, Turing e Church.

10 problemi di Hilbert.

Teoria della Complessità

Si fa distinzione tra problemi “semplici” e problemi “difficili”.

Anche di algoritmi efficienti e inefficienti.

Problemi del cammino hamiltoniano.

La teoria cerca di capire le ragioni di questa complessità.

Raggruppiamo in una classe tutti i problemi che possono essere risolti con algoritmi della stessa complessità. (Di tempo e di spazio)

La teoria della complessità analizza problemi solubili.

Scopo: quantificare le risorse in tempo e/o spazio necessarie a risolvere un problema dato, in funzione della taglia dell'input.

Classificare i problemi (solubili) in base alla difficoltà computazionale.

La classe P che corrisponde alla classe dei problemi risolvibili con un algoritmo di complessità in tempo polinomiale (caso peggiore) e la classe NP.

Uno dei più grandi problemi aperti dell'informatica P=NP?

Grafo Non Orientato

Una cammino è una sequenza di nodi, collegati da archi.

Un cammino semplice è un cammino che non contiene nodi ripetuti.

Un grafo è detto connesso se per ogni coppia di nodi esiste un cammino tra loro.

Un cammino è un ciclo se inizia e termina nello stesso nodo.

Un ciclo semplice è quello che contiene almeno tre nodi e ripete solo il primo e l'ultimo nodo.

Un grafo è un albero se è connesso e non ha cicli. I nodi di grado 1, ad eccezione della radice, sono chiamati foglie dell'albero.

Grafo Orientato

Ha frecce invece di nodi. Il numero di frecce che escono da un particolare nodo è detto grado uscente di quel nodo, quello entrante grado entrante.

Cammino orientato.

Fortemente connesso.

Linguaggio formale

Un linguaggio formale è un insieme di stringhe su un alfabeto, e L è un linguaggio sull'alfabeto Σ se L ⊆ Σ^*

N.B. I linguaggi possono essere insiemi finiti o infiniti.

L'insieme vuoto ∅ è il linguaggio che non contiene nessuna stringa.

∅ ∉ ∅

∅ ≠ {ε}

Operazioni sui linguaggi

I linguaggi sono insiemi, quindi possiamo applicare a essi le operazioni di unione, intersezione, differenza, complemento.

Prodotto di linguaggi

Dati due linguaggi S e T sull'alfabeto Σ, il prodotto (o concatenazione) di S e T è:

ST = S ○ T = {uv ∈ Σ^* | u ∈ S, v ∈ T}

ST è l'insieme di tutte le stringhe che sono concatenazione di una stringa in S e di una stringa in T.

S = {ε, a, a²} e T = {ε, a, b, a³} allora

ST = {ε, a, aa, ab, a², aaa, aab, a²b, a²a³} T_S= {a, a², aa, b, a² b, ab, ab² b, ab² a³}

ST ≠ T_S Ad esempio ab ∈ ST, ma non abba ∉ ST

Definizione formale di computazione

Sia M = (Q, Σ, δ, q₀, F) un automa finito e sia w = w₀w₁...w_m una stringa dove ogni w_i è un elemento dell'alfabeto Σ. Allora M accetta w se esiste una sequenza di stati r₀, r₁,..., r_m in Q con 3 condizioni:

1. r₀ = q₀
2. δ(r_i, w_i+1) = r_i+1, per i=0,...,m-1
3. r_m ∈ F

1) Afferma che la macchina inizia nello stato iniziale.2) Afferma che la macchina passa da stato a stato in base alla funzione di transizione.3) La macchina accetta l'input se termina la lettura in uno stato accettabile.

Diciamo che M riconosce il linguaggio A se A={w|M accetta w}

Teorema

La classe dei linguaggi regolari è chiusa rispetto all'operazione di intersezione

Dimostrazione

Siano L₁ e L₂ linguaggi regolari.

Supponiamo di avere un DFA A₁ = (Q₁, Σ, δ₁, q₀₁, F₁) ed un

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

A₁ riconosce L₁, cioè L₁ = L(A₁)

A₂ riconosce L₂, cioè L₂ = L(A₂)

L'obiettivo è quello di definire un DFA A che riconosca L₁ ∩ L₂.

Costruiamo A, dove A = (Q, Σ, δ, q₀, F)

1. Q = { (r₁, r₂) | r₁ ∈ Q₁ e r₂ ∈ Q₂ }
2. Σ
3. δ((r₁r₂), a) = (δ₁(r₁, a), δ₂(r₂, a))
4. q₀ = (q₀₁, q₀₂)
5. F = F₁ × F₂ // Questa è la differenza rispetto all'unione

Dimostrazione

Sia N = (Q, Σ, δ, q₀, F) l'NFA che riconosce il linguaggio A.

Costruiamo un DFA M = (Q', Σ, δ', q'₀, F') che riconosce A.

2 Casi:

• N non ha ε-archi
• N ha ε-archi

1^o Caso:

1. Q' = P(Q), [ogni stato di M è un insieme di stati di N]
2. Per R ∈ Q' e a ∈ Σ δ'(R,a) = {q ∈ Q | ∃ q ∈ δ(r,a)} per qualche r ∈ R oppure δ'(R,a) = ∪_r∈R δ(r,a)
3. q'₀ = ϵ_q0
4. F' = {R ∈ Q' | R contiene uno stato accettante di N}

2^o Caso:

Dobbiamo considerare gli ε-archi.

Per ogni stato R di M, definiamo E(R) come la collezione di stati che possono essere raggiunti dagli elementi di R proseguendo solo con ε-archi.

Per R ⊂ Q:

E(R) = {q | q pu`ò essere raggiunto da R attraverso 0 o più ε-archi}