Fondamenti dell'informatica - Appunti

ESERCITAZIONE (S)FONDAMENTI

Dimostrare che il linguaggio è regolare

L_ε{ xε{0,1}^* | 3 ∣ e(x) ∧ ∀ i eⁱ ≤ e(x) => i pari }

q₀ → q₁ → q₂ -1→ q₂ 0,1 q₃ 0,1_{q0 dispari} 1 pari in, sato pari, ma passo +, tenere nel linguaggio!!

L(M)={x | δˆ(q₀, x)εF} dobbiamo dimostrare che L ∼ L(M) per induzione su |x|

• xε L => xε L(M)
• x ¬ L => x ¬ L(M)

dame proprietà dell’ottoma :

• ∀x, δˆ(q₃, x)= q3
• δˆ(q₀, λ)^m) = { q₁ m dispari q₂ m pari}
• δˆ(q₁ λ^m)={ q₂ m dispari q₁ m pari}
• δˆ(q₂ λ^m)={ q₁ m dispari q₂ m pari}

dimostrama uno propriestà.

Base m=1

δˆ(q₀,1)=q₁

m=2 δˆ(q₀,1)= q₂

indicune su m : se m pari

δˆ(q₂,1)= q₂

se m dispari

δˆ(q₀,1^m+1)

δˆ(q₁ sub q₂).δˆ(q₂,1)=q_! q₁= q₁

torniamo alla dimostrazione principale

Base:

1x1=2

• x:1 ⊆ L
• δ(q₀,1)=q₂∉F
• x:10 ⊆ L
• δ(q₀,10)=q₂∉F
• x:0 ⊆ L
• δ(q₀,0)=q₁∉F
• x:00 ⊆ L
• δ(q₀,00)=q₀∉F

Induzione:

x∈L |x|=n ⇒ δˆ(q₀,x)=q₂ x∉L |x|=n ⇒ δˆ(q₀,x)∉F

|y|=n+1 y=x⌀ y=⌀0 y=⌀1

• se y∈L ∧ y=x⌀ ⇒ x∈L ⇒ δˆ(q₀,x)=q₂ ⇒ δˆ(q_{q, x⌀})=δ(q_2,⌀)=δ(q_{2,⌀)=q2∈F}
IP IND
• se y∉L ∧ y=x⌀ ⇒ x∉L ⇒ δˆ(q₀,x)=qˆ≠q₂
• δ(qˆ,⌀)₂f q₂ (ìm q₂ ci occotio scola leggendo en I )
• ⇒ δˆ(q₀,x⌀)∉F

• se y∈L ∧ y=⌀1 ⇒ x∈L ⇒ δˆ(q₀,x⌀)=qˆ≠q₂

x:⌀⌀^m ∧ despari (y∈L)

• δˆ(q₀,⌀⌀^m+1)=δ(q₂,⌀^m⌀1
• se x=⌀^m ⇒ δˆ(q₀,⌀^m⌀)=δ(q₂,⌀)_m

1. ( see x=⌀^m ⇒ δˆ(q₀,⌀^m)=δˆ(q₀,⌀^m⌀)=q₂)

• se y∉L ∧ y=⌀1 se x∈L δˆ(q₀,x⌀)=δ(q_2,⌀)-q₁∈F
• se x∉L se x:⌀^m ∨ ∃ i despari
• x: ⌀⌀⌀ⁱ⌀ⁱ
• δˆ(q0 i < 2 e i° segue da 1}

  Dimostrare che è regolare (ultima dimostrazione da riconoscere il linguaggio L)

  Stringa vuota di soli 1 e L

  Dobbiamo dimostrare in induz.sulle lungh della stringa che

  • x ∈ L => x ∈ L(M)
  • x ∉ L => x ∉ L(M)

  BASE | x | < 2

  • x:0 ∈ L δ(q₀,0) = q₄ ∈ F
  • x:1 ∈ L δ(q₀,1) = q₀ ∈ F
  • x:00 ∉ L δ(q₀, 00) => q₂ ∉ F
  • x:01 ∈ L => q₀ ∈ F
  • x:10 ∈ L => q₀ ∈ F
  • x:11 ∈ L => q₀ ∈ F

  IPOTESI INDUTTIVA

  • x ∈ L ∧ x:x’ x:0 => δ^(q₀, x) = q₄
  • x ∈ L ∧ x:x’ x:1 => δ^(q₀, x) = q₀
  • x ∉ L ∧ x:x’ x:00 => δ^(q₀, x) = q₂
  • x ∉ L ∧ x:x’ x:0*i*x’’ i > 2 => δ^(q₀, x) = q₃

  PASO

  1) x ∉ L x:x10 x' non contiene 0 i > 2

  per ipotesi induttiva |x'| = m δ^(q₀, x) = q₄

  s: 0 q_x:x0_x 10 ∉ L δ^(q₀ x:0) = δ(q₀, 0 = q₂ ∉ F

  s: x1 q_x:x1 ∈ L δ^(q₀ x:1) = δ(q₄, 1) = q₀∈ F

  2) x ∉ L x:x' x:l x' non ...

  per ipotesi induttiva δ^(q₀, x): q₀

  o y: x0 => y:x' x0 e ∉ 10

  δ^(q₀ x0): δ^(q₀:0)=q₄ ∈ F

  Ipotesi induttiva

  ESERCIZIO 2.3

  L = {x∈{0,1}^* | il numero di occorrenze di 0 è uguale al numero di occorrenze di 1}

  Il linguaggio non è regolare perchè accettare una stringa di questo linguaggio richiede tenere memoria del numero di occorrenze di 0 per poi contare le uguali occorrenze di 1.

  Per la dimostrazione formale utilizziamo il PUMPING LEMMA

  poniamo z = 0^k1^k

  ∀k∈ℕ. ∃z∈L. |z|≥k. ∀ u,v,w ε Σ^*. uwv=z (|uv|≤k, |v|>0)

  => ∃i. z’=uvⁱw ε L

  • u = 0^a
  • v = 0^b
  • w = 1^k

  con a+b=k e b>0

  uvⁱw = 0^a0^bi1^k = 0^a+b(i-1)1^k

  => quindi essendo x ipotesi b > 0 e a+b=k

  => solo per i ≠ 1 z ≠ L

  => L non regolare

  oppure: siccome |uv|≤k v può contenere solo zeri, quindi ∃i>1 la stringa uvⁱw contiene più zeri che uno (≠L)

  consideriamo |uv|=m

  z’ = uvⁱw = 0^k+m(i-1)1^k

  lnto punti m>0 , i>1 => k+m(i-1)>k =>z’≠L

  L non è regolare

  ho dimostrato quindi che se φεL esiste anche una sua derivazione

  adesso dobbiamo dimostrare la seconda implicazione

  S=>X allora XεL (se esiste una derivazione per X allora XεL)

  la minima derivazione possibile:

  BASE: S=>AB=>B=>A=>μεL

  PASO: S=>X S=>X'A'' X''=X

  c'è sicuramente una A che è unico simbolo che può terminare che può essere in qualunque posizione. supponiamo Xo che può essere dalla parti solo A (NO!) X'εL v X'Ο X''εL v X''=Οh S=>X'Aλ''X'ΟAx'''=>X'''Ο'εL

  • X'''Bx''=>λ'''AλX'''→λ'''X'A'''
  • K K+1 K+2
  • {λ′′λ′3′λ′λ′4′λ′λ′5′′λ′′ | λ′′λ′λ′}

  non è CF, lo dimostro con il pumping lemma (∀k &Exist;zεL |z|>K UVWXYZ W i W i

  ⇒&exists;eμ.un′µψεφ. γε∅ CF

  trovamo le possibili combinazioni di NWX

  se εεN 1, ella prima ripetizione esco del linguaggio considero puncti solo ε∅

  ESERCIZIO 3.1

  STRINGHE PALINDROME

  _G S → ε | 0_S0 | 1_S1 | 0 | 1

  x dimostrate che tale grammatica genera tutte e sole le stringhe palindrome dobbiamo dimostrare due implicazioni:

  1. _x ∈ _L allora _S ⇒ _x (induzione su |_x|)
  2. _S ⇒ _x allora _x ∈ _L (induzione su K lungh. della derivazione)
  1. BASE k=0 quindi x=ε allora _ε ⇒ _ε INDUZIONE ipotesi induttiva |y|_LK allora esiste _S→_y

     consideriamo |x|=k e palindromo → x=uN oppure x=u_λu

     con ∈{0,1} e _uN ∈{0,1}^* con _N=τ

     se x=u_λa a_N ─→ y=a_λN ancora palindrome e

     |y|_LK xché |x|=k

     quindi per ipotesi esiste _S→_y y=a_λN e quindi possiamo costuire una derivazione per _X:

     _S→_y﹦ _u λ_{S N}→ λ_S a_N →a_λN=_X

     abbiamo trovato quindi una derivazione per x

     se x= u_λN ─→ y=u_N ancora palindrome e M/K_LK xché |x|=k

     quindi x ipotesi induttiva esiste _S→_y φ e quindi

     _S→_uN→_uSN─→_uSu_N=_X

  1. la derivazione elementare è _S→_ε, _S→0, _S→1 BASE dove ε,0,1 sono tutte palindrome
  2. INDUZIONE: ipostesi induttiva _S→_x xè palindrome vediamo cosa succede con lunghezza K+1 se x palindromo se x= a_N oppure x= _ua_N

     u^λ=τ con ∧∈{0,1} se _S→_λS_N→_λ a_λN

     oppure _S→_uSN→_uSa_N

     con _a,b ∈ {0,1}