index předchozí 1 2 3 4 5 6 7 8 9 10 11 12 následující

Cvičení šesté

Normální tvary CFG, pumping lemma pro CFL

1) Odstraňte epsilon-pravidla :

   S => ABC
   A => AbA | BC
   B => bB | b | cBbAa | epsilon
   C => cD | c | Ab | epsilon
   D => SSS | b

   S => ABC
   A => Ab | BC
   B => bB | b | Ab | epsilon
   C => cD | c | Ac | epsilon
   D => SSS | cSAc

   S => 1X | Y1 | XZ
   X => 0YZ1 | S1X | Y
   Y => bB | 1 | X1 | epsilon
   Z => SZ | 0 |  epsilon

2) Význam konstrukce množin N_epsilon na příkladu

   A => BC | a | epsilon
   B => aB | ACC | b
   C => cC | AA | c

3) Odstraňte jednoduché pravidla

   S => X | Y
   A => bS | D
   D => ba
   B => Sa | a
   X => aAS | C 
   C => aD | S
   Y => SBb

Diskuse o významu N_A

4) Převeďte do Chomského normálního tvaru

   S => SaSbS | aAa | bBb
   A => aA | aaa | B | epsilon
   B => Bb | bb | b

   S => 0H1 | 1L0 | epsilon
   H => HH | 0H1 | LH | epsilon
   L => LL | 1L0 | HL | epsilon

5) Navrhněte gramatiku v CNF:

L = { a²ⁱb³ⁱc^j | i>=1, j>=0 }
L = { ww^R | w náleží {a,b}^* }

6) Nechť G je gramatika v CHNT. Nechť w náleží L(G), |w| = n. Jaká je délka odvození w v G?

7) Odstraňte levou rekurzi a transformujte do GNF

   S => Aa | Bb | aaA | SaA | SbB
   A => AAb | ab | SBb 
   B => Bbb | BBB | bAb

   S => A1 | 0 | 1B
   A => BS0 | 10 | SB0 
   B => 0B | B1B | S0

   S => Xc | Yd | Yb 
   X => Xb | a
   Y => Sa

   S => TTt | Tt | TS | s
   T => SsT | TsT | t

8) Transformujte do Greibachové NT
    A₁ => A₂A₃
    A₂ => A₃A₄ | A₁A₂
    A₃ => A₁a | b
    A₄ => bA₁ | A₄A₄
Výslednou gramatiku převeďte do 3-GNF.

9) Dokažte, že následující jazyky nejsou bezkontextové

L={ wcw | w náleží {a,b}^* }
L={ aⁿb^mcⁿd^m | n,m>=1 }