Automi e Linguaggi

Concetto di Stringa

Alfabeto: insieme finito di simboli

Stringa: sequenza finita di caratteri nell'alfabeto

• Σ = { 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 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: le stringhe più corte precede la più lunga, a parti c'è ordine lessicografico (alfa < beta, alfa > beta)

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, ...}

cerlastinpevuotonon appartiene

Prendo m ∈ N = (101011001)₂ e mi chiedo => "101011001" ∈ L ?

Esercizio:

Consideriamo un automa M:

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

Q = {q₁, q₂}

Σ = {0, 1}

q₀ = q₁ stato iniziale

F = {q₂}

Rappresentazione

L(M)?

Tutte le stringhe che terminano in 1

Queste operazioni conservano la regolarità del linguaggio:

Teorema:

Se A e B sono linguaggi regolari,

Allora: A ∪ B ⇒ Linguaggio regolare

Dim:

Ip₁: A, B linguaggi sullo stesso alfabeto

Ip₂: A regolare ⇒ ∃ DFA M₁ = {Q₁, Σ, δ₁, q₁, F₁}:

L(M₁) = A

B regolare ⇒ ∃ DFA M₂ = {Q₂, Σ, δ₂, q₂, F₂}:

L(M₂) = B

Idea: ∃ M = (Q, Σ, δ, q₀, F)

Q = Q₁ × Q₂

Σ = comune

δ((q₁, q₂), δ) = (δ₁(q₁, δ), δ₂(q₂, δ))

q₀ = (q₁, q₂) une coppia

F = (F₁ × Q₂) ∪ (Q₁ × F₂)

Esercizio:

Mostra un NFA che accetta ogni stringa binaria che ha un 1 nella 3^a posizione dalla fine

1. 000 ∉ L
2. 01000 ∉ L
3. 10000100 ∈ L

L'automa sceglie

Non c'è nulla

ACCETTO

può fare in entrando in

equivalente

NFA ≡ DFA

R⁺ ≡ R R^* linguaggio costituito da tutte le sequenze di 1 o più elementi del linguaggio di R

R^k = R o R o ... o R

R ϵ = R stringa vuota ≠ insieme vuoto

R Ø = Ø

R ∪ ϵ L(R) ∪ {ϵ} = potrebbe essere diverso

R ∪ Ø L(R) ∪ Ø = L(R)

_L(Ø)

QUIZ

Ø^*

L(Ø^*) = ?

=>(L(Ø))^* = Ø^* = ϵ

sequenza di 0 elementi

Teorema (Relazione tra linguaggi ed espressioni regolari)

Un linguaggio L è regolare <=> ∃ REX t.c. il linguaggio generato: L(R) = L

Abbiamo dimostrato:

• ∀ REX => L(R) è regolare

Dobbiamo dimostrare =>

Se L regolare => ∃ REX R t.c L(R)=L

Idea:

• GNFA
• da cui è possibile definire
• REX
• DFA
• L regolare

Una GNFA è costruibile da un DFA, ogni linguaggio regolare è riconosciuto da un DFA. Da ogni linguaggio regolare possiamo costruire e definire una REX.

Esercizio:

Dato un DEA qual è la REX?

Convertiamolo in un GNFA:

Eliminiamo il nodo 2.

Non giusto

Se A

xz e A

caso i=0

x yⁱ z => xz

y⁰ = ε

i = 4

Perché questo teorema è vero:

A regolare => ∃ DFA

|Q| = p

M è capace di contare soltanto fino a p

Se A |s| ≥ p

q₀ → q₁ → ... → q_n ∈ F

≥ p

“principio delle piccionaia”