From The Blog, Page 5

Automa a stati finiti deterministico (DFA)

Symbol	Meaning
Q	finite set called the States
Σ	finite state called Alphabet
δ:QxΣ→Q	transition function
q0∈Q	start state
F⊆Q	Set of accepted states

Linguaggio regolare

Un linguaggio è detto linguaggio regolare se è riconosciuto da un automa a stati finiti.

Operazioni regolari

Siano A e B due linguaggi. Definiamo le operazioni regolari unione, concatenazione e star così:

• Union: A ∪ B = {x|x∈A or x∈B}
• Concatenation: A ○ B = {xy | x∈A and y∈B}
• Star: A* = {x₁, x₂, x₃,...x_k | k ≥ 0 and each x_i∈A }

Inoltre si definisce per prassi ε stringa vuota (in maniera simile a quello che in SQL è NULL)

Automa a stati finiti non deterministico (NFA)

Symbol	Meaning
Q	finite set called the States
Σ	finite state called Alphabet
δ:QxΣε→P(Q)	transition function
q0∈Q	start state
F⊆Q	Set of accepted states

Espressione regolare

Un'espressione regolare può essere

• a per qualche a nell'alfabeto Σ
• ε
• ∅
• (R₁∪R₂), con R₁, R₂ espressioni regolari
• (R₁○R₂), con R₁, R₂ espressioni regolari
• (R₁^*), con R₁ espressione regolare

Se u, v, w sono stringhe di variabili e terminali, e A → v è una regola della grammatica, diciamo che uAv produce uwv, scritto uAv ⇒ uwv.

Diciamo che u deriva v, scritto

$u\stackrel{*}{\Rightarrow }v$

se u = v oppure se esiste una sequenza, con k ≥ 0, u₁ ⇒ u₂ ⇒ u₃ ⇒ ...u_k ⇒ v.

Grammatica context-free (CFG)

V	Un insieme finito di variabili
Σ	Un insieme finito, disgiunto da V, di terminali
R	Un insieme finito di regole, ciascuna costituita da una variabile e una stringa di variabili e terminali
S∈V	La variabile di partenza

Forma normale di Chomsky

Una grammatica context-free è in forma normale di Chomsky se ogni regola è nella forma

A → BC

A → a

dove a è ogni terminale e A, B, C sono ogni variabile, eccetto che B e C non sono variabili di partenza. In aggiunta, permettiamo la regola S → ε, dove S è la variabile di partenza.

Pushdown automa

Symbol	Meaning
Q	finite set called the States
Σε	input Alphabet
Γε	stack Alphabet
δ:QxΣεxΓε→P(Q, Γε)	transition function
q0∈Q	start state
F⊆Q	Set of accepted states

Macchina di Turing

Una macchina di Turing è una 7-tupla, (Q, Σ, Γ, δ, q₀, q_accepted, q_rejected), dove Q, Σ, Γ sono tutti insiemi finiti e

Symbol	Meaning
Q	insieme finito di stati
Σ	alfabeto che non contiene il simbolo "blank" ˽
Γ	alfabeto del nastro, dove ˽ ∈ Γ e Σ ⊆ Γ
δ:QxΓ→Q x Γ x {L, R}	funzione di transizione
q0∈Q	stato di partenza
qaccepted	stato accettato
qrejected	stato rifiutato

Con q_accepted ≠ q_rejected

Teorema	Codice (Sipser)	Pagina (Sipser)	Link alla dimostrazione (Italiano)
La classe di linguaggi regolari è chiuso per l'operazione di unione	1.25	45
La classe di linguaggi regolari è chiuso per l'operazione di concatenazione	1.26	47
Ogni automa finito nondeterministico ha un automa finito deterministico corrispondente	1.39	55
(Corollario) Un linguaggio è regolare se e solo se qualche automa finito nondeterministico lo riconosce	1.40	56
La classe dei linguaggi regolari è chiusa per l'operazione di unione	1.45	59
La classe dei linguaggi regolari è chiusa per l'operazione di concatenazione	1.47	60
La classe dei linguaggi regolari è chiusa per l'operazione di star	1.49	62
Un linguaggio è regolare se e solo se qualche espressione regolare lo descrive	1.54	66
(Lemma) Se un linguaggio è regolare, allora è descritto da un'espressione regolare	1.60	69
Pumping lemma: se A è un linguaggio regolare, allora c'è un numero p (la lunghezza "pump") per cui, se s è una stringa in A di lunghezza come minimo p, allora s può essere divisa in tre pezzi, s = xyz, che soddisfano le seguenti condizioni: ∀ i ≥ 0, xyiz ∈ A |y| > 0 |xy| ≤ p	1.70	78
Ogni linguaggio senza contesto è generato da una grammatica senza contesto in una forma normale di Chomsky	2.9	107
Un linguaggio è senza contesto se qualche automa pushdown lo riconosce	2.20	115
(Lemma) Se un automa pushdown riconosce qualche linguaggio, allora è senza contesto	2.27	119
(Claim) Se Apq genera x, allora x può portare P da p con stack vuoto a q con stack vuoto	2.30	121
(Claim) Se x può portare P da p con stack vuoto a q con stack vuoto, Apq genera x	2.31	121
Pumping lemma per linguaggi senza contesto: se A è un linguaggio senza contesto, allora c'è un numero p (la lunghezza "pump") per cui, se s è una stringa in A di lunghezza come minimo p, allora s può essere divisa in cinque pezzi, s = uvxyz, che soddisfano le seguenti condizioni: ∀ i ≥ 0, uvixyiz ∈ A |vy| > 0 |vxy| ≤ p	2.34	123
Ogni macchina di Turing multinastro ha un'equivalente macchina di Turing a singolo nastro	3.13	149
(Corollario) Un linguaggio è Turing-riconoscibile se e solo se qualche macchina multinastro di Turing lo riconosce	3.15	150
(Corollario) Un linguaggio è Turing-riconoscibile se e solo se qualche macchina di Turing nondeterministica lo riconosce	3.18	152
(Corollario) Un linguaggio è decidibile se e solo se qualche macchina nondeterministica di Turing lo decide	3.19	152
Un linguaggio è Turing-riconoscibile se e solo se qualche enumeratore lo enumera	3.21	153
ADFA è un linguaggio decidibile	4.1	166
ANFA è un linguaggio decidibile	4.2	167
AREX è un linguaggio decidibile	4.3	168
EDFA è un linguaggio decidibile	4.4	168
EQDFA è un linguaggio decidibile	4.5	169
ACFG è un linguaggio decidibile	4.7	170
ECFG è un linguaggio decidibile	4.8	171
Ogni linguaggio senza contesto è decidibile	4.9	172
ATM è indecidibile	4.11	174
R è incontabile	4.17	177
(Corollario) Alcuni linguaggi non sono Turing-riconoscibili	4.18	178
Un linguiaggio è decidibile se e solo se è Turing-riconoscibile e co-Turing-riconoscibile	4.22	181
(Corollario) ATM non è Turing-riconoscibile	4.23	182
HALTTM è indecidibile	5.1	188
ETM è indecidibile	5.2	189
REGULARTM è indecidibile	5.3	191
EQTM è indecidibile	5.4	192
(Lemma) Sia M un LBA con q stati e g simboli nell'alfabeto del nastro. Ci sono esattamente qngn distinte configurazioni di M per un nastro di lunghezza n	5.8	194
ALBA è decidibile	5.9	194

 

Un automa finito nondeterministico generalizzato è un NFA con delle espressioni regolari al posto dei semplici membri dell'alfabeto Σ.

Si usa, per prassi:

• Lo stato iniziale ha frecce uscenti verso tutti gli altri stati, ma non ha frecce entranti;
• C'è un solo stato di accettazione, ha solo frecce entranti da ogni altro stato e non ha frecce uscenti. Inoltre non coincide con lo stato iniziale;
• A parte gli stati iniziale e finale, ogni stato ha una freccia che va verso ciascuno degli altri stati e una verso se stesso.

La definizione formale di GNFA è

Symbol	Meaning
Q	finite set called the States
Σ	finite state called Alphabet
δ:(Q-{qaccept})x(Q-{qstart})→R	transition function (tutte le combinazioni possibili, tranne quelle che partono dallo stato accettato e finiscono nello stato di partenza)
qstart∈Q	start state
qaccept	accepted states

La conversione di una GNFA in una DFA consiste in un semplice algoritmo:
CONVERT(G)

• sia k il numero di stati di G
• se k = 2 allora G deve essere uno stato di start, uno stato di accept e una sola freccia contenente un'espressione regolare
• se invece k > 2, allora si calcola Q' = Q - q_rip, cioè per ogni stato diverso da start e accept, si convertono le frecce in un equivalente senza lo stato rip:
  δ'(q_i, q_j) = (R1)(R2)*(R3)∪(R4), dove:
• • R1 = δ(q_i, q_rip)
  • R2 = δ(q_rip, q_rip)
  • R3 = δ(q_rip, q_j)
  • R4 = δ(q_i, q_j)
• si applica CONVERT a G'

Un'espressione regolare può essere

• a per qualche a nell'alfabeto Σ
• ε
• ∅
• (R₁∪R₂), con R₁, R₂ espressioni regolari
• (R₁○R₂), con R₁, R₂ espressioni regolari
• (R₁^*), con R₁ espressione regolare

Per chi viene dal mondo dei database è facile capire la differenza - sottile - tra ε e ∅: la prima rappresenta un insieme contenente una sola stringa vuota (SET @var = ''), mentre il secondo rappresenta un insieme vuoto (SET @var = NULL).

L'insieme degli stati possibili in una DFA è l'insieme delle combinazioni degli stati di una NFA, incluso insieme vuoto.

Per esempio, con un insieme di stati di una NFA {1, 2, 3}, si ottiene un insieme di stati DFA {∅, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}}

A questo punto compilo la tabella stati / alfabeto in base alle specifiche di NFA.

Le DFA e le NFA sono equivalenti, cioè ciascuna delle due può esprimere esattamente gli automi espressi dall'altra, ma ci sono alcune differenze:

• DFA deve illustrare tutte le possibili combinazioni di stati. In altre parole, per ogni stato Q_n, si devono esplorare tutti gli elementi dell'alfabeto, mentre in una NFA uno stato può non essere espresso esplicitamente.
• NFA può avere, nello stesso stato, più volte lo stesso valore di alfabeto. In questo caso è necessario creare più thread, ciascuno dei quali è valido. Mentre in una DFA l'elemento accettato Q_n ∈ F ⊆ Q è uno, in una NFA può essere più di uno (da chiarire! Se fosse così, gli automi non sarebbero equivalenti!)
• NFA ha un valore supplementare nell'alfabeto: ε, che rappresenta una stringa vuota. Se uno stato ha una freccia ε uscente, si creano due thread, uno sullo stato corrente e uno sullo stato di destinazione di ε.

Tra le due definizioni - simili - ci sono alcune piccole differenze.
Questa è la definizione formale di NFA

Symbol	Meaning	Example
Q	finite set called the States	Come per DFA
Σ	finite state called Alphabet	Come per DFA
δ:QxΣε→P(Q)	transition function	P(Q) è il powerset di Q, cioè l'insieme di tutte le combinazioni di Q. Σε rappresenta l'alfabeto arricchito di epsilon.
q0∈Q	start state	Come per DFA
F⊆Q	Set of accepted states	Come per DFA

Union: A ∪ B = {x|x∈A or x∈B}

Concatenation: A ○ B = {xy | x∈A and y∈B}

Star: A* = {x₁, x₂, x₃,...x_k | k ≥ 0 and each x_i∈A }

 

Inoltre si definisce per prassi ε stringa vuota (in maniera simile a quello che in SQL è NULL)

 

La prova dell'unione di A con B è data dalle seguenti cinque considerazioni:

1. Gli stati possibili sono dati dal prodotto cartesiano degli stati A × B: Q = {(r₁, r₂) | r₁∈A and r₂∈B}
2. Σ per ora lo consideriamo un unico dizionario per entrambe le macchine
3. δ è una funzione definita su una coppia di stati alla volta: δ((r₁, r₂), a) = (δ(r₁, a), δ(r₂, a)). Ovviamente lo stato restituito è un elemento di Q, che a sua volta è costituito da "coppie".
4. q₀ = (q₁, q₂)
5. Il risultato è un F = (F₁ × Q₂) ∪ (F₂ × Q₁)

Nota: il risultato NON è F₁ × F₂, perché questo rappresenterebbe l'intersezione dei due automi, e non l'unione, perché entrambi gli stati di uscita dovrebbero essere validi.

Symbol	Meaning	Example
Q	finite set called the States	sciacquo, carico, centrifuga, scarico, lavaggio
Σ	finite state called Alphabet	on, off, error
δ:QxΣ→Q	transition function	carico x on → lavaggio
q0∈Q	start state	scarico
F⊆Q	Set of accepted states	scarico finale

Un automa a stati finiti può accettare o non accettare una serie ordinata di valori del dizionario.
Dato un entrypoint (quello definito come q₀), se al termine della serie di valori sono arrivato a un elemento Q appartenente a F, allora la serie è valida ed è accettata dall'algoritmo, altrimenti no.

Per esempio, questo:

è un automa descrivibile come: ({q₁, q₂}, {0,1}, δ, q₁, q₂})

dove δ è definito come

	0	1
q1	q1	q2
q2	q1	q2

in questo automa, la sequenza 100 non è valida, perché termina su un elemento che non è uno stato accettato (cioè non appartiene a F).

1101 invece termina in q₂, che appartiene a F. Quindi 1101 è una sequenza accettata.

Il significato dell'automa - non sempre così facile da comprendere - è che le uniche stringhe accettate sono quelle che terminano con 1.

L(M) = {w | w ends in a 1}

I simboli principali sono:

Simbolo	Codice html	Significato
⇒	⇒	Implica. Se la parte sinistra è vera, allora è vera anche la parte destra
⇔ ↔	⇔ ↔	Se e solo se (SSe). Se la parte sinistra è vera, allora è vera anche la parte destra e viceversa. a b a∧b V V V V F F F V F F F V
¬	¬	Negazione (operatore unario)
∧	∧	And: la proposizione è vera solo se sono veri entrambi i termini a b a∧b V V V V F F F V F F F F
∨	∨	Or: la proposizione è vera se è vero almeno uno dei termini a b a∧b V V V V F V F V V F F F
⊕	⊕	Or esclusivo: la proposizione è vera se i due termini sono differenti. è complementare a SSe a b a∧b V V F V F V F V V F F F

Lo studio della "teoria della computazione", o come viene chiamata all'UniVe, Calcolabilità e Linguaggi Formali, riguarda tre argomenti:

• Complessità
• Calcolabilità
• Automi

La complessità indaga i costi di esecuzione degli algoritmi, in particolare li suddivide in classi, le cui principali sono polinomiale ed esponenziale.

La calcolabilità riguarda quali problemi siano risolvibili da un computer: per esempio, se risolvi un problema la risposta è che si può, ma se per ora non riesci non puoi sapere se il motivo è che non hai elaborato abbastanza oppure se è proprio interminabile.

Gli automi definiscono quali sono le caratteristiche di una macchina in grado di calcolare.