Skip to content

Latest commit

 

History

History
227 lines (134 loc) · 7.56 KB

Tutorato4_180404.md

File metadata and controls

227 lines (134 loc) · 7.56 KB
Raw

Grammatiche CFG

Es dalle slide 1 CFG

Es 5.1.1.d

Scrivere una CFG per Ld = {insieme delle stringhe in {0,1}* con numero di 0 doppio del numero di 1}

S => S0S0S1S | S0S1S0S | S1S0S0S | ε

Ora va dimostrato che w ∈ Ld se e solo se (<=>) S *=> w DIMOSTRAZIONE:

SE (<=) (Se una stringa è in L(S), allora contiene un numero di 0 doppio di quello degli 1)

Si procede per induzione sul numero di passi di derivazione.

CASO BASE: n = 1

Allora w = ε che ∈ Ld.

INDUZIONE: n ≥ 2

L'ipotesi induttiva è che l'enunciato sia corretto per n passi di derivazione. Pertanto si suppone che se S *=> x in n passi allora x ha #0 doppio di #1.

Siano x1, x2, x3, x4 stringhe prodotte da S in n passi di derivazione. Allora con un passo in più si possono produrre le stringhe:

  1. S => S0S0S1S (n)=> x10x20x31x4
  2. S => S0S1S0S (n)=> x10x21x30x4
  3. S => S1S0S0S (n)=> x11x20x30x4

Queste stringhe hanno tutte il corretto numero di 0 e 1, se è valida l'ipotesi induttiva.

Per dimosrare il SE, torna utile questo lemma.

Lemma utile

Ogni stringa in Ld (escluso ε) è formata da triple t1t2...tk e contiene almeno una sottostringa con due 0 e un 1, ovvero una sottostringa fra:

  • 001
  • 010
  • 100.

DIMOSTRAZIONE del lemma:

Ovviamente per stringhe come 001 010 è banalmente vero visto che sono formate proprio da quelle stringhe. Ma ad esempio 000 110 non è formata da tali stringhe, anche se è in Ld.

Se una stringa non è costituita da nessuna tripla fra quelle elencate sopra, allora deve essere costituita di triple con due o tre 1. Ma allora per essere in Ld dovrà anche avere qualche tripla di soli 0, per 'compensare' gli 1. Ma concatenando triple con due o tre 1 con triple 000 sicuramente otterremo almeno una tripla con due 0 e un 1 (come ad esempio nella stringa 000 110 = 0 001 10). Per cui ∀ w ∈ Ld, w sarà nella forma x m y dove xy ∈ Ld e m = 001/010/100.

SOLO SE (=>) (Se una stringa contiene un numero di 0 doppio di quello degli 1 allora è in L(S))

CASO BASE: |w| = 0 ==> w = ε che ∈ L(S).

INDUZIONE: |w| ≥ 1

Suppongo che esistano produzioni per generare tutte le stringhe in Ld di lunghezza 3*n (sono sempre multipli di 3 per il lemma sopra). Dimostro che è possibile generare qualunque stringa w di lunghezza 3*(n+1). Allora per il lemma precedentemente dimostrato w = x m y e xy ∈ Ld e m = 001/010/100. Allora uso l'ipotesi induttiva su xy. Per cui esiste una produzione S *=> xy. Più precisamente, per come sono fatte le produzioni, S genererà una cosa in questa forma: S *=> x S y, visto che fra ogni coppia di terminali c'è una variabile S.

A questo punto basta inserire la stringa m con una delle tre produzioni, togliendo le S in eccesso con la produzione S => ε

Esercizio 3 pag 25 slides

Scrivere una CFG per L.

L = {anbm | 0 ≤ n ≤ m ≤ 2n}

Grammatica:

  • S => aSBb | ε
  • B => b | ε

Va dimostrato che w ∈ L <=> w è generata da S.

Dimostro =>

Per induzione su |w|= n.

CASO BASE:

  • |w| = 0. Allora w = ε e c'è la produzione S => ε

INDUZIONE: (n ≥ 2)

Allora se ho una stringa w ∈ L e |w| ≥ 2, può essere scritta in (almeno) una delle due forme:

  1. w1 = a x b, con x ∈ L.
  2. w2 = a y bb, con y ∈ L.

Allora suppongo per ipotesi induttiva che sia x che y siano generate da S.

Quindi posso usare queste produzioni, nei rispettivi casi, per ottenere w1 e w2:

  1. S => aSBb => a x B b => a x b = w1.
  2. S => aSBb => a y B b => a y bb = w2.

Dimostro <=

Per induzione su n = # di passi di derivazione.

CASO BASE:

  • n = 1: S => ε, che è una stringa del linguaggio.

INDUZIONE: n ≥ 2

S => aSBb (n-1)=> a x B b.

Uso l'ipotesi induttiva per sostenere che x ∈ L. Allora, a seconda della produzione di B, ottengo:

  1. axb
  2. axbb

sono entrambi in L.

Altri esercizi

Esercizio T1 (da esame)

S => aB

B => Ab | b

A => aB | a

Data la CFG, definire il suo linguaggio. E dimostrare induttivamente che S genera tale linguaggio.

A produce stringhe anbm con n = m+1 oppure n = m, n > 0 e m ≥ 0. Chiamo il linguaggio K. B produce stringhe anbm con m = n+1 oppure n = m, m > 0 e n ≥ 0. Chiamo il linguaggio J.

S allora produce il linguaggio L = {w | w = anbm con n = m oppure n = m+1 con n e m > 0}.

Ora va dimostrato che w ∈ L(S) <=> w ∈ L. Conviene però prima dimostrare induttivamente che le variabili A e B producono il liguaggi K e J, poi, sapendo questo, segue facilmente che S genera tutte e sole le stringhe in L.

DIMOSTRAZIONE: A e B producono stringhe in (ripettivamente) K e J.

Devo dimostrare che:

  1. w è prodotta da A => w ∈ K.
  2. w è prodotta da B => w ∈ J.

CASO BASE 1 passo: A => a e B => b che sono stringhe in K e J.

INDUZIONE 2+ passi: Assumiamo che valga l'ipotesi induttiva per stringhe prodotte in n ≥ 1 passi.

A => aB (n)=> ax. Allora x ∈ J per ipotesi induttiva. Allora ax è generata in n+1 passi e sicuramente ∈ K perchè aggiungendo una 'a' davanti semplicemente o pareggio il numero di 'a' e 'b', oppure avrò una 'a' in più.

B => Ab (n)=> xa. Su x vale l'ipotesi induttiva perchè è prodotta da A in 'n' passi.

DIMOSTRAZIONE: Qualunque stringa in K e J è prodotta da A e B

CASO BASE: |w| = 1. w = a e w = b che sono generate.

INDUZIONE |w| ≥ 2:

Devo dimostrare che:

  1. w1 ∈ K => w1 è prodotta da A.
  2. w2 ∈ J => w2 è prodotta da B.

Sia n = |w1| = |w2|

Siano:

  • w1 ∈ L(A)
  • w2 ∈ L(B)

Allora:

  • w1 = a x1 con x1 = anbm con m = n oppure m = n+1, m > 0 e n ≥ 0.
  • w2 = x2 b con x2 = anbm con n = m oppure n = m+1, n > 0 e m ≥ 0.

Quindi x1 ∈ J e x2 ∈ K.

Suppongo per ipotesi induttiva che i punti 1 e 2 siano validi per stringhe lunghe n-1.

Allora A *=> x2 e B *=> x1.

E quindi w1 e w2, che contengono almento due simboli sono prodotte da:

  1. A => aB *=> a x1 = w1
  2. B => Ab *=> x2 b = w2

Quindi è possibile generare qualunuqe stringa in K e J.

Dimostrazione di S.

S produce tutte le stringhe di B con una a all'inizio. Segue che la definizione di L è corretta.

Es 5.1.7.a libro

Considero la CFG: S => aS | Sb | a | b

Dimostrare per induzione sulla lunghezza delle stringhe che nessuna sringa w in L(S) ha ba come sottostringa.

CASO BASE: |w| = 1 e |w| = 2

  • w = a
  • w = b
  • w = aa
  • w = ab
  • w = bb

Non si può generare ba.

INDUZIONE: |w| ≥ 2

Suppongo che tutte le stringhe lunghe n non contengano ba. Allora:

  1. S => aS *=> ax = w
  2. S => Sb *=> xb = w

Allora se x non contiene ba in entrambi i casi anche w non conterrà ba.