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

Cvičení páté

Uzávěrové vlastnosti R, bezkontextové gramatiky

1) Rozhodněte, zda platí:
     jsou-li jazyky L₁, L₂, L₃,... regulární, pak i jazyk sjednocení_i=1,2,... L_i je regulární jazyk.

2) Najděte takovou posloupnost regulárních jazyků L₁, L₂, L₃,... aby jazyk průnik_i=1,2,... L_i
     nebyl regulární. (DÚ)

3) Nechť L₁, L₂ jsou neregulární jazyky nad abecedou {a,b}^*.
     Dokažte nebo vyvraťte, zda je či není regulární:

L₁ průnik L₂
L₁ sjednoceno L₂ (DÚ)
L₁ - L₂ (DÚ)
L₁ zřetězeno L₂ (DÚ)
L₁^* (DÚ)
L₁^C (DÚ)

4) Nechť L₁ je regulární a L₁ průnik L₂ je neregulární jazyk. Platí, že jazyk L₂ je nutně neregulární?

5) Platí následující implikace?

L₁ je regulární, L₂ je neregulární => L₁ průnik L₂ je neregulární
L₁ je regulární, L₂ je neregulární => L₁ průnik L₂ je regulární
L₁ je regulární, L₂ je neregulární => L₁ - L₂ je neregulární (DÚ)
L₁ je regulární, L₂ je neregulární => L₁ - L₂ je regulární (DÚ)
L₁ je regulární, L₂ je neregulární => L₂ - L₁ je neregulární (DÚ)
L₁ je regulární, L₂ je neregulární => L₂ - L₁ je regulární (DÚ)

6) Def: operace @ rozšířeného sjednocení dvou jazyků takto:
   L₁ @ L₂ = { u . v | u,v náleží (L₁ sjednoceno L₂)}
   Dokažte, že jestliže jsou jazyky L₁ a L₂ regulární, pak i jazyk L₁ @ L₂ je regulární.
   Dále najděte dva takové neregulární jazyky L₁ a L₂, aby jazyk L₁ @ L₂ byl regulární.

7) Nechť L je regulární jazyk. Dokažte, že jazyky L^# jsou regulární:

L^# = { v | existuje u takové, že u.v náleží L }
L^# = { w | existuje x,y,z takové, že y náleží L a w=xyz }

8) Def: Homomorfismus h:
         h(epsilon)= epsilon
         h(u.v)= h(u).h(v) pro všechny u,v z abecedy na *

     Def: Nechť L je jazyk, pak h(L) = { w | w = h(u) kde u náleží L }

     Def: Inverzní Homomorfismus
         h^-1(y) = { x náleží abeceda^* | h(x) = y }
         h^-1(L) = { x náleží abeceda^* | h(x) náleží L }

     Příklad
        h(a)=01
        h(b)=011 pak

h(abb) = 01011011
h^-1(0101011)={aab}
h^-1(0010)={}
pokud navíc h(c) = epsilon pak h^-1(01011) = c^cac^*bc^*

Ukažte, že R je uzavřena na h, h^-1.

9) Nechť je dána abeceda {a,b,c} a homomorfismus h; h(a)=ac, h(b)=cb, h(c)=ca. Určete:

h(aabc), h(cbaa)
h^-1(cccaaccb), h^-1(accba)
h(L), L = {aⁿbⁿcⁿ| n>0}

10) Nechť je dána abeceda {a,b,c} a homomorfismus h; h(a)=aa, h(b)=ba, h(c)=a. Určete:

h^-1(aabaaabaa)
h(L), L = { w náleží {a^*,b^*} | #_a(w) = #_b(w)}
h^-1(L), L = { w náleží {a^*} | |w| = 2k, k náleží N}

11) Dokažte nebo vyvraťte

h(L₁.L₂) = h(L₁).h(L₂)
h(L₁ sjednoceno L₂) = h(L₁) sjednoceno h(L₂)
h( (L₁.L₂)^R ) = h(L₁^R).h(L₂^R)
h(L₁ průnik L₂) = h(L₁) průnik h(L₂)
h ( h(L) ) = h (L)
h^-1 ( h(L) ) = L
h^-1(L₁.L₂) = h^-1(L₁) . h^-1(L₂)
h^-1(L₁ sjednoceno L₂) = h^-1(L₁) sjednoceno h^-1(L₂)
h^-1(L₁ průnik L₂) = h^-1(L₁) průnik h^-1(L₂)

12) Navrhněte bezkontextové gramatiky pro jazyky:

L={ ww^R | w náleží {a,b,c}^* }
L={ w | w náleží {a,b,c}^*, w=w^R }
L={ a³ⁿ⁺²b²ⁿ | n>=2 }
L={ aⁿbⁿb^m+1c^m-1 | n>=0, m>=1 }
L={ aⁿb^mc^mdⁿ | n,m>=0 }
L={ uxw | u,x,v náleží {a,b,c}^*, uv=(uv)^R, x=caⁿb²ⁿc}
L={ w | w náleží {a,b}^*, #_a(w) > #_b(w)}
L={ w | w náleží {a,b}^*, #_a(w) = 2 * #_b(w)}

13) Co generují tyto gramatiky?

   S => aB | bA | epsilon
   A => aS | bAA
   B => bS | aBB

```
   S => aAS | a
   A => ba | Sba
```

14) Pro následující gramatiku

   S => AaB | BaA
   A => AB  | a
   B => BB  | b

najděte derivační strom s výsledkem bbbbaa
je tento strom určený jednoznačně?
kolik různých nejlevějích odvození má slovo bbbbaa
je gramatika jednoznačná?
je jazyk L(G) jednoznačný?

15) Odpovězte zda pro

  S => SSS | a

je gramatika jednoznačná?
je jazyk L(G) jednoznačný?

16) Navrhněte jednoznačnou gramatiku generující jazyk
L={ww^R | w náleí {a,b}^*} sjednoceno {a^2k | k>=1 }

17) Navrhněte gramatiky pro jazyky L, jsou gramatiky jednoznačné ?

L={aⁱb^jc^k | i,j,k >= 1, i=j nebo j<>k}

18) Najděte ekvivalentní redukovanou gramatiku ke gramatice této:

   S => aA  | bB
   A => aAB | aa | AC | AE
   B => bBA | bb | CB | BF
   C => DE
   D => cc | DD
   E => FF | FE
   F => EcE

19) Je jazyk generovaný gramatikou G bezkontextový?

  G:  S => xT
      T => Sx
    xTx => y