Druha sada domacich uloh

Uloha 1

Nech L = {w | # w + # w = # w} je jazyk nad abecedou {a,b,c}
               a     b     c
Najdite vsetky homomorfizmy h take, ze h(L) = L.
(# w je pocet znakov a v slove w)
  a

Uloha 2

Nech L  a L  su jazyky. Rozhodnite, ci plati:
      1    2

          *   *    * *
  (L U L ) = L (L L )
    1   2     1  2 1

Uloha 3

Zostrojte gramatiku pre jazyk:

 L = {w | w je cislo v desiatkovej sustave delitelne 7}

Uloha 4

Zostrojte gramatiku pre jazyk:

                   R   
 (b) L = {w | w = w } ; L je nad abecedou {a,b}

Uloha 5

Zostrojte REGULARNU gramatiku pre jazyk:

           *  *  * *     *  *  * *
     L = (0 10 10 )  ^ (1 01 01 )

Uloha 6

Zostrojte gramatiku pre jazyk:

            n m 2m n+1
     L = { a b c  d   | m,n >= 0 }

Uloha 7

Zostrojte REGULARNU gramatiku pre jazyk:

     L ={w | w obsahuje podslovo abba} ; L je nad abecedou {a,b}

Uloha 8

Popiste jazyk generovany gramatikou
G = ({S,A,B,C},{a,b,c},P,S)
P = { S -> AS | BS | CS
      CS -> c
      Aa -> aa
      Ab -> ab
      Bb -> bb
      Bc -> bc
      Cc -> cc