Automi e Linguaggi

Concetto di STRINGA:

Alfabeto: insieme finito di simboli (Σ)

STRINGA: sequenza finita di caratteri nell'alfabeto (in Σ)

Σ = {a, b, c, d, ..., z}

st2 = "aabbccde"

Σ* = {tutte le stringhe costruibili in Σ}

• lunghezza: cardinalità
• stringa nulla: stringa senza simbolo (" ") lunghezza 0 (e)
• sottostringa: caratteri di una stringa ne formano un'altra
• concatenazione: tutti i caratteri di 1 più tutti i caratteri di un'altra
• ordine lessicografico: ordine degli elementi dell'alfabeto (alfa < beta, a precede b)
• ordine di stringa: se stringa x costa precede la + lunga, a parità c’è ordine lessicografico (alfa < beta, alfa > beta)

Concetto di STRINGA:

Alfabeto: insieme finito di simboli ( )

STRINGA: sequenza finita di caratteri nell'alfabeto (in )

= {a,b,c,d,...,z}

st2 = "aabbccde"

= {tutte le stringhe costruibili in }

• lunghezza: cardinalità
• stringa nulla: stringa senza simbolo ("") lunghezza 0( )
• sottostringa: caratteri di una stringa formano un'altra
• concatenazione: tutti i caratteri di i più tutti i caratteri di wildre
• ordine lessicografico: ordine degli elementi dell'alfabeto (alfa < beta, a precede b)
• ordine di stringa: le stringhe + corte precede la + lunga, a parità c'è ordine lessicografico (alfa < beta, alfa > b it)

LINGUAGGIO (sopra un certo alfabeto)

=: sottoinsieme di stringhe sopra un alfabeto Σ

L ⊆ Σ^*

Es:

Σ = {0,1} => Σ^* = {ε, 0, 1, 00, 01, 10, 11, ...}

L = {w ∈ Σ^* | w codifica in binario un numero divisibile per 3 }

L = {0, 11, 110, 1001, ...} (la stringa vuota NON appartiene)

Prendo n ∈ N = (1010101)₂ e mi chiedo => "1010101" ∈ L?

Con 2 bit di memorizzazione posso rappresentare 4 stati:

00, 01, 10, 11

Da ogni stato, a seconda del numero che leggo dopo, si passa da

uno stato ad un altro o si rimane nello stesso

Questa rappresentazione è quella di

una macchina a stati finiti (4 stati)

e c'è quindi uno stretto collegamento

con la rappresentazione di un calcolatore

Automa a stati finiti (DFA)

Def: macchina astratta costituita da 5 elementi:

Ψ = (Q, Σ, δ, q₀, F)

• Q: stati interni della macchina (q_i i∈N)
• Σ: alfabeto che la macchina può interpretare
• δ: funzione da uno stato e un simbolo a un nuovo stato => Q×Σ —> Q TRANSIZIONE
• q₀: stato di input prima di leggere la sequenza
• F: sottoinsieme di stati. (stati di accettazione, la stringa viene accettata se fa parte di questi sottostati.)

Q = {q₀, q₁, q₂, q₃}

Σ = {0, 1}

δ = (le frecce) :

q₀ ∈ Q

F : {q₁}

Lingua riconosciuta da una macchina:

L(M) = {w ∈ Σ* | M accetta w}

Una macchina riconosce solo il linguaggio (nessun ε)

F = ∅ ⇒ L(M) = ∅

F = Q ⇒ L(M) = Σ*

Esercizio:

Consideriamo un automa M:

M = { Q, Σ, δ, q₀, F }

Q = { q₁, q₂ }

Σ = { 0, 1 }

δ =

• 0 1
• q₁ q₁ q₂
• q₂ q₁ q₂

q₀ = q₁ stato iniziale

F = { q₂ }

Rappresentazione

L(M)?

Tutte le stringhe che terminano in 1

Consideriamo una macchina

M'¹ = (Q, Σ, δ, q₁, F¹)

Uguale ad M, ma

F¹ = {q₁}

L(M'¹) = {w ∈ Σ^* | w termina in 0, oppure è ε}

Accettazione di un Automa:

Dato un AUTOMA A STATI FINITI (DFA):

M = { Q, Σ , δ , q₀, F } M accetta w ∈ Σ^* se

∃ una sequenza di stati : r₀, r₁, r₂, r₃, ..., r_m