9. Sada domacich uloh

Uloha 1 (prez)

a) Pre dany TS A najdite bezkontextove jazyky L   a L   take, ze pre jazyk
                                            A1    A2
platnych vypoctov stroja A plati:
                                       L      =  L   prienik  L
                                        PV(A)     A1           A2

b) S vyuzitim LPV(A) dokazte ze problem prazdnosti prieniku bezkontextovych jazykov je nerozhodnutelny

c) S vyuzitim LPV(A) dokazte ze problem ci je bezkontextovy jazyk rovny Sigma* je nerozhodnutelny

 

Uloha 2 (prez)

S vyuzitim LPV(A) dokazte ze pre lubovolne bezkontextove gramatiky G1, G2 je nerohodnutelne

  1. L(G1)c je bezkontextove
  2. L(G1) prienik L(G2) je bezkontextove

Uloha 3 (prez)

Dokazte ze pre LDPD A a regularny jazyk R je rozhodnutelne

  1. L(A) = R
  2. L(A) \podmnozina R
  3. R \podmnozina L(A)

 

Uloha 4 (prez)

Dokazte ci su nasledujuce vlastnosti rek. Vycislitelnych jazykov rozhodnutelne

  1. konecnot
  2. regularnost
  3. bezkontextovost

Rozhodnite ci su nasledujuce problemy ciastocne rozhodnutelne

  1. rovnost prazdemu jazyku
  2. rovnost Sigma*
  3. rekurzivnost
  4. nerovnost prazdnemu jazyku

 

Uloha 5

Dokazte ci su nasledujuce vlastnosti rek. vycislitelnych jazykov ciastocne rozhodnutelne

    1. |L| = 1
    2. |L| >= 10
    3. L nie je rkurzivny
    4. L je regularny
    5. w \ in L pre dane L
    6. L1 prienik L2 je prazdne
    7. L1 - L2 je prazdne