Prva sada domacich uloh

Uloha 1

Dokazte alebo vyvratte nasledovne tvrdenia:

                                               *    ?    *   *
(a) Pre jazyky L  a L  plati rovnost    (L  L )     =   L   L
                1    2                    1  2           1   2

                                                      *    *
(b) Existuju jazyky L  a L  take, ze prienik jazykov L  a L  je konecny.
                     1    2                           1    2

Uloha 2

Dokazte alebo vyvratte nasledovne tvrdenia:

                            *
(a) Ak pre jazyk L plati L=L , potom L=LL.

                                        *
(b) Ak pre jazyk L plati L=LL, potom L=L .

(c) Ak pre jazyk L plati LL=LLL, potom L=LL.

Uloha 3

Nech h je homomorfizmus a L, L  a L  nech su jazyky. Dokazte alebo
                              1    2

vyvratte, ze pre lubovolne h, L ,L ,L platia nasledovne identity:
                               1  2

             *  *      ?         *  *      *  *
(a)      h( L  L )     =    (h( L ))  (h( L ))
             1  2                1         2

                       ?
(b)      h( L ^ L )    =    h( L ) ^ h( L )       (znak ^ znamena prienik)
             1   2              1        2

Uloha 4

Nech h je homomorfizmus a L, L  a L  nech su jazyky. Dokazte alebo
                              1    2
 
vyvratte, ze pre lubovolne h, L ,L ,L platia nasledovne identity:
                               1  2

          -1           ?    -1         -1
(a)      h  ( L ^ L )  =   h  ( L ) ^ h  ( L )
               1   2             1          2

             -1        ?
(b)      h( h  (L))    =   L

          -1           ?
(c)      h  ( h(L))    =   L

Uloha 5

Ak h  a h  su homomorfizmy, je aj  (h o h  ) homomorfizmus?
    1    2                           1   2

(o je skladanie zobrazeni)

Uloha 6

                                           *  *  *  *        *  *  *  *
Slovne popiste, ake slova tvoria jazyk  ( 0 10 10  )   ^  ( 1 01 01  ) ,

kde ^ je prienik a 0, resp. 1  je skrateny zapis pre {0}, resp. {1}.