Fondamenti dell'informatica - Appunti

Name: Fondamenti dell'informatica - Appunti
Brand: Skuola.net
Price: 7.99 EUR
Availability: InStock
Rating: 4.0 (2 reviews)
Author: albertom

Revisionato il 11/04/2026

di albertom

Publisher

Vota 4,0/5 (2)

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

Appunti di Fondamenti dell'informatica per l’esame del professor Giacobazzi. Gli argomenti trattati sono i seguenti: la dimostrazione della regolarità del linguaggio, dimostrare che …

Esame Fondamenti dell'informatica

Facoltà Scienze matematiche fisiche e naturali

Dal corso del Prof. Giacobazzi Roberto

Università Università degli Studi di Verona

A.A. 2013-2014

82 pagine

2 download

Appunto

Scarica

Estratto del documento

Base:

x:1λ ∉L
x:10 ∉L
x:0λ ∉L
x:00 ∉L

Induzione:

x∈L |x|=m ⇒ δ(q₀,x)=q₂

x∉L |x|=m ⇒ δ(q₀,x)∉F

|y|=m+1 y=x0_λ ⇒ y=x0 y=x1

se y∈L ∧ y=x0 ⇒ x∈L ⇒ δ(q₀,x)=q₂ ⇒ δ(q_e,x0)=δ(q₂,0)=q₂∈F

se y∉L ∧ y=x0 ⇒ x∉L ⇒ δ(q₀,x)=q₁≠q₂

δ(q₁,0)∉q₂

⇒ δ(q₀,x0)∉F

se y∈L ∧ y=x1 ⇒ x∈L ⇒ δ(q₀,x)=q₁≠q₂

x: x0^λm dispari ⇒ δ(q₀, x0^λ1^m) = δ(q₂,0^{1^m}) = δ(q₁,1^m) = q₂

(se x: 0^m ⇒ δ(q₀,0^{1^m}) = δ(q₁,0^λ) = q₂)

se x∉L ∧ y=x1 ⇒ δ(q₀,x1)=δ(q₂,1)=q₂∉F

se x∉L ⇒ x:0^m ∨ ∃i dispari : x:x0_i0x_i

δ(q₀,x1) = δ(q₀,1)=q₁∉F

δ(q₀,x0)_i0ⁱ0x_i ⇒

se δ(q₀,x0ⁱ)=q₃ ⇒ δ(q₀,x0ⁱ0x_i)=q₃

se δ(q₀,x0)_i∉{q₀,q₂}

L = {0ⁿ 2^m 1^m | m ∈ N}

L: 0^k 1^j 1ⁱ 2^k

1^k ⟹ 1 j ≤ k

⟹ ∃ N ∈ O ^k N = O^m m > 0

w: 0^m j 0ⁿ 1^m k-(m,n,m) 2^k

u: O^m

v: ^I

w: ^J

2k = 2(mμ + iιm + k - m - μm)

2k = 2m(i - ι) + 2k

2m(i - ι) = 0

m non può essere = 0 xchè |w| > 0

FALSO |w|>1

quindi uⁱv^j ∉ L ⟹ L non regolare !!

ε·x1 => y = x'u e d

ipotesi induttiva

3) x∊, x = x₀x₁...

ipotesi induttiva δ(q₀, x) = q₂

y = x₀ y = x'1000 ∉ L
y = x1 y = x'1001 ∈ L

ipotesi induttiva

δ(q₀, x₀) = δ(q₂, 0) = q₃ ∉ L
δ(q₀, x₁) = δ(q₂, 1) = q₀ ∈ L

4) x∊L x = xⁱ0ⁱ1ⁱ i > 2

ipotesi induttiva δ(q₀, x) = q₃

y = xs ∈ L

MINIMIZZAZIONE:

stato non finali

comportamento

possiamo ridisegnare l'automa

se lwt dispari -> X_h+hwrl = 0 = X_ht+h+1

uguale al suo simmetrico ma h+ht dispari

=> 2ⁱ ∉ L

se lwt pari -> X_h+hwrl = 0 = X_h+hw+1+2

oggetto indice dispari uguale al suo simmetrico

=> 2ⁱ ∉ L

L₂ = {X ∈ |0,A|^* | X| = 2m

∀i < m X_i ≠ X_2m+i}

O_M ed O_M1 e _L i simmetrici sono sempre diversi tra loro

z = O^k1^k

zⁱ = u_M2^Mò = O_KHW_LJ^k

devo guardare che aggiungendo O_M1 HW non vede + lo simmetrica

O_M dimostrato diversamente.!! anche se stesso strusge

lwt > 0 -> lwt dispari -> 2ⁱ ∉ L

lwt pari lwt > 2 lwt = 2m

zⁱ = O_K O_mO_M1^k

il cento dello struzzo è più e

2^K+M = 2^K+M+A = 0

uguale al suo simmetrico => 2ⁱ∉ L

(L₂) REGOLARE

L = {aⁿb^m | n, m ≥ 1} ∪ {a}

è intuitivamente un linguaggio regolare quindi costruisco l'automa M

L(M): { x | δ(q₀, x) ∈ F }

linguaggio riconosciuto dell'automa M

dobbiamo dimostrare che L = L(M) quindi che:

x ∈ L ⇒ x ∈ L(M)
x ∉ L ⇒ x ∉ L(M)

BASE |x| = 1

x = a ∈ L ⇒ δ(q₀, a) = q₄ ∈ F
x = b ∉ L ⇒ δ(q₀, b) = q₂ ∉ F

BASE |x| = 2

x = aa ∉ L δ(q₀, aa) = q₃ ∉ F
x = ab ∈ L δ(q₀, ab) = q₄ ∈ F
x = ba ∉ L δ(q₀, ba) = q₄ ∈ F
x = bb ∉ L δ(q₀, bb) = q₂ ∉ F

INDUZIONE: |x| = M

x ∈ L ⇒ δ(q₀, x) ∈ F
x ¬

Anteprima

Vedrai una selezione di 18 pagine su 82