Appunti quaderno di Automi e linguaggi

Stato di accettazione:

Particolare stato di una macchina che ha il compito di indicare la condizione di verità.

• Se alla fine dell'esecuzione capito nello stato di accettazione allora la condizione che sto verificando è vera, altrimenti falsa.

Esempio:

È possibile costruire una macchina con memoria di 2 bit che verifichi se una stringa di bit rappresentanti un numero in base 2 costituisca un multiplo di 3.

Memoria di 2 bit ⇒ 4 stati

Una prima ipotesi:

Questo primo automa funziona a patto che la stringa in ingresso non sia vuota.

In tal caso l'esecuzione parte dallo stato iniziale q₁ e lo esamina

Esempio corretto:

LEZIONE 2

LINGUAGGI:

ALPHABET: Σ FINITE SET OF "SYMBOLS", NOT EMPTY (Σ ≠ 0)

STRING OVER Σ: FINITE SEQUENCE OF SYMBOLS IN Σ

-e.g. Σ = {a, b, c … z} STRING ⇒ "aabcada" Σ* = {"a", "b" … "aa" … }

Σ* = { ALL STRINGS OVER Σ }

LENGTH OF A STRING: # OF SYMBOLS

NULL STRING ε: STRING WITH NO SYMBOLS e.g. " " ε ∈ Σ* |_{Lungta 1}|

SUBSTRING: UNA STRINGA È UNA SOTTOSTRINGA DI UN’ALTRA SE I CARATTERI CHE COMPONGONO LA SOTTOSTRINGA COMPAIONO NELLO STESSO ORDINE NELLA STRINGA DI PARTENZA

CONCATENATION: LA CONCATENAZIONE DI DUE STRINGHE CREA UNA NUOVA STRINGA COSTITUITA DA TUTTI I CARATTERI DELLA PRIMA STRINGA ORDINATI CONSECUTIVI SEGUITI DAI CARATTERI DELLA 2^a STRINGA ORDINATI

LESSICOGRAPHICAL ORDER: ALFA < BETA GLI ELEMENTI DELL'ALFABETO SONO ORDINATI QUINDI SI PUÒ DEFINIRE UN ORDINE DI PRECEDENZA

STRING ORDER: ( SHORTEST ORDER) UNA STRINGA PIÙ CORTA PRECEDE SEMPRE UNA PIÙ LUNGA, A PARITÀ DI LUNGHEZZA SI UTILIZZA ORDINE LESSICOGRAFICO PER STABILIRE L'ORDINAMENTO

ALFA < BETA_{4 4} ALFA > BIT _{4 34 3}

LANGUAGE OVER Σ: SUBSET OF STRING OVER Σ [ L ⊂ Σ* ]

-e.g. Σ = { 0, 1, 2 } Σ* = { ε, 0, 1, 00, 01 … }

L = { w ∈ Σ* | w ENCODES IN B NARY A NUMBER DIVISIBLE BY 3 }

L: { 0, 11, 110, 1001 … } ε ∉ L 1 ∉ L

[UN LINGUAGGIO RAPPRESENTA LE ISTANZE CHE SODDISFANO UN CERTO QUESITO]

-nel nostro esempio: m ∈ ℕ ( 0, 1, 0, 1, 0, 1 )₂ ⇒ "011010" ∈ L ⟨ sì ⟩⟨ no ⟩

THM:

A, B regular languages, then A∘B is regular

Utilizzando la stessa impostazione di prima

• Σ = {0,1}
• A = {01, 001}
• B = {10, 101}

Faccio una concatenazione

0101 ∈ A∘B ha 01101 ∉ A∘B

DEF:

NFA → nondeterministic FA

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

δ: Q x (Σ ∪ {ε}) → (Q) = 2^Q

(9.6) |—> {q_i, q_i', ...} ⊆ Q

6 ∈ Σ ∨ 6 = ε

∅ ∈ 2^Q

DEF:

Accepting computation NFA

1. r₀ = q₀
2. ∀ i: 0...m-1 , r_i+1 ∈ δ(r_i, y_i+1) with y_i+1 ∈ Σ ∨ y_i+1 = ω_s
3. r_m ∈ F

L'automa non è obbligato a consumare un simbolo dell'input per ogni transizione (cambiamento di stato) caso y_i+1 = ε

L'automa può scegliere se transitare autonomamente in 'q' oppure consumare un simbolo σ ed andare in q'

Come se l'automa decidesse di portare le due computazioni avanti in parallelo

da q leggendo σ l'automa può decidere se andare in q₀ o q₁, c'è una scelta

In un DEA non c'è una scelta da compiere e non si può non consumare un simbolo

1) a   L(a) = {a}

2) ε   L(ε) = {ε}

3) ∅   L(∅) = ∅

Induction Step: |R| = n   per costruire RE più lunghe di n uso le operazioni:

1. (R1 ∪ R2)   |R1| ≤ m   |R2| ≤ m   L(R1) ∪ L(R2)
2. (R1 ∘ R2)   ✓   regular languages are closed under concatenation
3. (R1)^*   ✓   regular languages are closed under Kleene's star

Es: RE (ab ∪ a)^*   Σ = {a, b}

"ababaa" -> stringa generata dall'ESPRESSIONE regolare

A regualr ⇒ ∃ DFA

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

|x| ≥ p M contiene p stati.

M is able to "count" only up to p

S ⊂ A |S| ≥ p

q₀ → q₁ → q_m ∈ F

|x| ≥ 2

Ci deve essere un loop all'interno non accettare stringhe lunghe 2

A regualr ⇒ ∃ DFA M = (Q, Σ, δ, q₀, F)

P = |Q|

S ⊂ A |S| ≥ p S = s₁ s₂ ... s_m m ≥ p

M(S) r₀ r₁ ... r_m ∈ F m ≥ p

κ_i+1 = δ(r_i, s_i+1)

Per il principio della piccionaia ci deve essere un q ripetuto

X = s₁ ... s₃Y = s₃+1 ... s_xZ = s_x+1 ... s_m

(1) ∀i_≥0 xⁱz ∈ A

M(xz) = Π (s₁ ... s₃, s_m+1 ... s_m)

(2) |y| > 0

|y| ≥ 1 dato che &&con;

(3) |xy| = |s₁ ... s_m| = k ≤ p per ipotesi

Lezione 5

Pumping Lemma

A regualr ⇒ ∃ p∀ s ∈ A, |s| ≥ p

∀ subdivision s = xyz

• |xy| ≤ P

• |y| > 0

∀i ≥ 0: xyⁱz ∈ A

A is not regular

Assume that L is regular ("by contradiction") ⇒ P applies ⇒ ∃ p > 0

Find s ∈ L per cui non è possibile applicare il pumping lemma

Lo stato q_i: vedra` 2 trans. usc. tramite con h₂ quindi diventa non deterministica

Other proof:

A reguar ⟹ ∃ r_ex r st L(r_ex) = A

h: Σ → Γ"

r_ex = Σ ∪ {(), *, o, u} = Σ'

Γ' = Γ ∪ {(), *, o, u}

h: Σ' → Γ'*

δ ⇢ h(δ) δ ∈ Σ

δ ⇢ δ δ ∉ Σ

Es:

Σ = {0, 1, 2} Γ = {a, b} h(0) = ab h(1) = ba

r = 0*1(o ∪ 1)* = (((o)*o.1).(o ∪ 1)*)

h(r) = (ab)*ba(abub₀*)

h(A) = h(L(r)) = L(h(r))

Lᵢ by induction on |r|

h(A) ∈ reguar

Reguar languages: DFA, NFA, GNFA, r_ex

B = {0ⁿ1^m | n ≥ 0} is not reguar, ∃ un sistema per tali linguaggi?

Context-Free Grammar (CFG):

Def:

A CFG is a tuple (V, Σ, R, S)

V "variables" Σ "terminals" R "production rules"

i simboli che non possono essere ulterioramente sostituiti

Lᵢ le regole di sostituzione

S ∈ V "start variabile"

Es:   ⱼ = (V, Σ, R, S)

V: {A, B} Σ: {o, 1, 2} S = A

• A → oA2
• A → B
• B → ε