Matematické Fórum

a) slova L1 a L2 se musí někde lišit. Pokud se liší na i-té pozici, jsou tvaru
x=v0w
y=r1s
nebo
x=v1w
y=r0s

kde |v|=|r|=i-1

proto slovo x#y je tvaru v0w#r1s nebo v1w#r0s
pro kořenový neterminál tedy máme přepisovací pravidla
S=N1C | J0C
kde C je cokoliv (tedy C=eps|Z|ZC, kde Z=0|1), N je 0C# "obalené" slovy délky i-1,
J je 1C# "obalené" slovy délky i-1
N=0C|ZNZ
N=1C|ZNZ

b) pokud se x liší od y na i-té pozici, je hledané slovo tvaru u0vr1s nebo u1vr0s, kde |u|=|r|=i-1, |v|=|s|=|x|-i. Můžeme si odtud všimnout že |u|+|s|=|v|+|r|. Můžme proto položit vr=pq, kde |p|=|u|, |q|=|s|. Slovo z jazyka je pak u0pq1s nebo u1pq0s, přitom u1p je jednička "obalená" stejným počtem znaků z obou stran, podobně q0s.

Gramatika proto může vypadat takto:
S=JN|NJ
J=1|ZJZ
N=0|ZNZ
Z=0|1