Zadania ostatniej szansy, JAO, ZSI, 1999
        ----------------------------------------

1. Czy jezyk { w*w^r : w dowolne slowo nad alfabetem A } jest beazkontekstowy?
Czy jest regularny? Nalezy rozwazyc dowolny skonczony alfabet A.
Gwiazdka oznacza konkatenacje.

2. Czy dla kazdego jezyka bezkontekstowego L, jezyk
Pref(L) = { w : istnieje v takie, ze w*v nalezy do L } jest rowniez 
bezkontekstowy?

3. Czy istnieje jezyk bezkontekstowy nie akceptowany przez zaden deterministyczny
automat ze stosem?

4. Czy dla dowolnych jezykow regularnych L1, L2 nad alfabetem A, jezyk 
Shuffle(L1,L2), zdefiniowany nizej, jest tez regularny?

  Definicja jezyka Shuffle(L1,L2):

  Mowimy ze slowo w jest przeplotem slow v, u jesli
  albo
  w = w'*a, v = v'*a dla pewnej litery a z alfabetu i slowo w' jest przeplotem slow v' i u
  albo
  w = w'*a, u = u'*a dla pewnej litery a z alfabetu i slowo w' jest przeplotem slow v i u'
  albo
  w = v, u jest slowem pustym
  albo
  w = u, v jest slowem pustym

  Definiujemy Shuffle(L1,L2) = { w : w jest przeplotem pewnego slowa v z L1
                                     i pewnego slowa u z L2 }