Date: Fri, 10 Dec 1999 15:38:36 +0200
Subject: Riesenie prezentacie (oprava)

9.13.
* uz som to raz poslal, ale s malou chybou - R, ktore som povazoval za symbol
abecedy totiz znamena reverz. Nejak podstatne to vsak nic nemeni. *
                          
L={u#vR#w|u,v,w su binarne zapisy cisel a plati w=u+w} nie je bezkontextovy
jazyk.
Dokaz: Pomocou lemy o vkladani.
Predpokladame, ze L je bezkontextovy.
Nech n>p, n>q (p,q z lemy o vkladani)
Nech z=1^n#1^n#1^n0
z patri L, lebo 2^n-1+2^n-1=2^(n+1)-2
-xvy z lemy o vkladani musi obsahovat druhy # (rovna sa), lebo inak by sme 
vkladanim zmenili len lavu alebo len pravu stranu rovnosti u+v=w
-# patri v, inak by sme dostali viacnasobny vyskyt #, nez povoluje definicia
jazyka L
-0 nepatri xvy, lebo inak by xvy obsahovalo podslovo #1^n0, ktoreho dlzka je
vacsia nez q
Z uvedeneho vyplyva:
x=1^a, y=1^b, kde a<>0, b<>0
Podla lemy o vkladani ma platit:
1^n#1^(n+ai)#1^(n+bi)0 (pre vsetky i)
2^n-1+2^(n+ia)-1=2^(n+ib)-2
Upravami dostaneme:
1+2^(ai)=2^(bi)=>
=>ai=0, bi=0 => a=0, b=0 (spor)