Calcolabilità e linguaggi formali, Page 4 Categoria

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.