Knuth-Bendixov algoritem: zgledi

<< kb.m

Splosne grupe

Aksiomi grupe: asociativnost, leva enota, levi inverz

levagrupa  =  {f[2][f[1],  v[1]]  ->  
            v[1],  f[2][f[3][v[1]],  v[1]]  ->  
            f[1],  f[2][f[2][v[1],  v[2]],  v[3]]  ->  f[2][
              v[1],  f[2][v[2],  v[3]]]};
d  =  {0,  2,  1};
w  =  {1,  0,  0};

levagrupa  =  Napolni[levagrupa, d, w, True];

ReduciranaOblika["(abc)~", levagrupa, d, True]

ReduciranaOblika["(ab)~(ac)", levagrupa, d, True]

ReduciranaOblika["(f~g)~c(fc)~g", levagrupa, d, True]

ReduciranaOblika["(((a~b)~c)~d)~(ac)~bd", levagrupa, d, 
      True]

Aksiomi grupe: asociativnost, desna enota, desni inverz

\(\(desnagrupa\  = \ {\(f[2]\)[v[1], \ f[1]]\  -> \ 
            v[1], \ \(f[2]\)[v[1], \ \(f[3]\)[v[1]]]\  -> \ 
            f[1], \ \(f[2]\)
\ \ \ \ \ \ [\(f[2]\)[v[1], \ v[2]], \ 
              v[3]]\  -> \ \(f[2]\)[
              v[1], \ \(f[2]\)[v[2], \ v[3]]]};\)\)

Napolni[desnagrupa, d, w, True];

Obicajni aksiomi grupe

\(\(obicajnagrupa\  = \ {\(f[2]\)[f[1], \ v[1]]\  -> \ 
            v[1], \ \(f[2]\)[\(f[3]\)[v[1]], \ v[1]]\  -> \ 
            f[1], \ \(f[2]\)[v[1], \ f[1]]\  -> \ 
            v[1], \ \(f[2]\)[v[1], \ \(f[3]\)[v[1]]]\  -> \ 
            f[1], \ \(f[2]\)
\ \ \ \ \ \ [\(f[2]\)[v[1], \ v[2]], \ 
              v[3]]\  -> \ \(f[2]\)[
              v[1], \ \(f[2]\)[v[2], \ v[3]]]};\)\)

Napolni[obicajnagrupa, d, w, True];

Krajsanje na levi

krajsaj = {f[2][f[3][v[1]],  f[2][v[1],  v[2]]]  ->  
            v[2]};

krajsaj = Napolni[krajsaj, d, w, True];

Dve levi enoti

enacbe = {f[3][f[3][v[1],  v[2]],  v[3]]  ->  f[3][
              v[1],  f[3][v[2],  v[3]]],  f[3][f[1],  
              v[1]]  ->  v[1],  f[3][f[2],  v[1]]  ->  
            v[1],  f[3][f[4][v[1]],  v[1]]  ->  
            f[1],  f[3][f[5][v[1]],  v[1]]  ->  
            f[2]};
d  =  {0,  0,  2,  1,  1};
w  =  {1,  1,  0,  1,  0};

Napolni[enacbe, d, w, False];

Levi in desni inverz

enacbe  =  {f[2][f[1],  v[1]]  ->  
            v[1], f[2][f[3][v[1]],  v[1]]  ->  
            f[1], f[2][v[1],  f[4][v[1]]]  ->  
            f[1],  f[2][f[2][v[1],  v[2]],  v[3]]  ->  f[2][
              v[1],  f[2][v[2],  v[3]]]};
d  =  {0,  2,  1,  1};
w  =  {1,  0,  1,  0};

Napolni[enacbe, d, w, False];

Podatkovne strukture

Sklad

d = 0:   f1 = 0
d = 0:   f2 = lambda
d = 2:   f3 = push
d = 1:   f4 = pop
d = 2:   f5 = concatenate
d = 1:   f6 = top

sklad = {f[6][f[3][f[1],  v[1]]]  ->  
            f[1],  f[4][f[3][f[1],  v[1]]]  ->  
            v[1],  f[5][f[2],  v[1]]  ->  
            v[1],  f[5][f[3][f[1],  v[1]],  v[2]]  ->  f[3][
              f[1],  f[5][v[1],  v[2]]]};
d  =  {0,  0,  2,  1,  2,  1};
w  =  {1,  1,  0,  1,  0,  0};

Napolni[sklad, d, w, False];

ReduciranaOblika["f5f3f1f2f3f1f4f4f3f1f3f1f3f1f2", sklad, d, 
      False]

ReduciranaOblika["f6f2", sklad, d, False]

Formalni jeziki

Dvojiški nizi

01 > 0, 10 > 0, 00 > 1

pravila = {f[3][f[1], f[2]] -> 
            f[1], f[3][f[2], f[1]] -> 
            f[1], f[3][f[1], f[1]] -> 
            f[2], f[3][f[3][v[1], v[2]], v[3]] -> f[3][
              v[1], f[3][v[2] , v[3]]]};
d = {0, 0, 2};
w = {1, 1, 0};

napolnitev = Napolni[pravila, d, w, False];

ReduciranaOblika["f3f3f3f3f1f2f1f1f2", napolnitev, d, 
      False]

ReduciranaOblika["f3f3f3f3f3f2f1f2f2f1f2", napolnitev, d, 
      False]

Koncno predstavljene grupe

Kleinov cetvercek

Klein4 = 
        NapolniGrupo[{"SS=e", "TT=e", "STST=e"}];

SeznamElementovGrupe[Klein4]

ReducirajElementGrupe[Klein4, "TS"]

ReducirajElementGrupe[Klein4, "TTTTSSSTTTSSSSSSS"]

Ciklicne grupe

C3

C3 = NapolniGrupo[{"SSS=e"}];

SeznamElementovGrupe[C3]

ReducirajElementGrupe[C3, "SSSSSSSS"]

C5

C5 = NapolniGrupo[{"SSSSS=e"}];

SeznamElementovGrupe[C5]

ReducirajElementGrupe[C5, "SSSSSSSS"]

Diedrske grupe

D3

D3 = 
        NapolniGrupo[{"SSS=e", "TT=e", "STST=e"}];

SeznamElementovGrupe[D3]

ReducirajElementGrupe[D3, "SST"]

ReducirajElementGrupe[D3, "STSSTS"]

D4

D4 = 
        NapolniGrupo[{"SSSS=e", "TT=e", "STST=e"}];

SeznamElementovGrupe[D4]

ReducirajElementGrupe[D4, "TSSS"]

ReducirajElementGrupe[D4, "STSSTS"]

Kristalografske grupe

P1

P1 = NapolniGrupo[{"TSR=e", "RST=e"}];

SeznamElementovGrupe[P1]

ReducirajElementGrupe[P1, "SST"]

ReducirajElementGrupe[P1, "STSSTS"]

ReducirajElementGrupe[P1, "RSSSSTR"]

P2

\(\(P2 = 
        NapolniGrupo[{"RR=e", "SS=e", "TT=e", "RSTRST=e"}];\)\)

\(\(P2 = 
        NapolniGrupo[{"RR=e", "SS=e", "TT=e", "UU=e", "RSTU=e"}];\)\)

SeznamElementovGrupe[P2]

ReducirajElementGrupe[P2, "SST"]

ReducirajElementGrupe[P2, "STSSTS"]

ReducirajElementGrupe[P2, "RSSSSTR"]

ReducirajElementGrupe[
      P2, "TSRSRSRSRSRSRT"]

P3

\(\(P3 = 
        NapolniGrupo[{"RRR=e", "SSS=e", "TTT=e", "RST=e"}];\)\)

SeznamElementovGrupe[P3]

ReducirajElementGrupe[P3, "SST"]

ReducirajElementGrupe[P3, "STSSTS"]

ReducirajElementGrupe[P3, "RSSSSTR"]

Pg

Pg = NapolniGrupo[{"RR=SS"}];

Pg = NapolniGrupo[{"RRS~S~=e"}];