Automi e Linguaggi

Name: Automi e Linguaggi
Rating: 5.0 (2 reviews)
Author: miccigia

Revisionato il 17/07/2026

di miccigia

Publisher

Vota 5,0/5 (2)

Contenuto verificato e approvato dal Team di Esperti di Skuola.net

Appunti del corso svolto 2020/2021 online, con integrazioni dell'anno accademico successivo, in presenza. Coprono l'intero programma, con esercizi e del tutto similari alle sue dispense non …

Esame Automi e linguaggi

Facoltà Ingegneria

Dal corso del Prof. Cesati Marco

Università Università degli Studi di Roma Tor Vergata

A.A. 2020-2021

268 pagine

3 download

Appunto

Scarica

Estratto del documento

Concetto di stringa

Alfabeto e 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 Σ}

Caratteristiche delle stringhe

Lunghezza: cardinalità

Stringa nulla: stringa senza simbolo (" ") lunghezza 0 (e)

Sottostringa: caratteri di una stringa ne formano un'altra

Concatenazione: tutti i caratteri di una più tutti i caratteri di un'altra

Ordine lessicografico: ordine degli elementi dell'alfabeto (alfa < beta, a precede b)

Ordine di stringa: se la stringa x è più corta precede la più lunga, a parità c’è ordine lessicografico (alfa < beta, alfa > beta)

Linguaggio e automa a stati finiti

Linguaggio

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?

Automa a stati finiti (DFA)

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

Definizione di 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 Transizioni
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) :

	0	1
q₀	q₁	q₂
q₁	q₁	q₂
q₂	q₃	q₁
q₃	q₂	q₃

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'¹

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

Anteprima

Vedrai una selezione di 10 pagine su 268