###################################################################### ##GRW: Save this file as GRW. To use it, stay in the # ##same directory, get into Maple (by typing: maple ) # ##and then type: read GRW : # ##Then follow the instructions given there # ## # ##Written by Doron Zeilberger, Rutgers University , # #zeilberg@math.rutgers.edu. # ###################################################################### #Created: Feb. 17, 2003 #This version: Feb. 17, 2003 #GRW: A Maple package to compute regular expressions from type-3 grammars #Please report bugs to zeilberg@math.rutgers.edu print(`Created: Feb. 17, 2003.`): print(`This version: Feb. 17, 2003`): lprint(``): print(`Written by Doron Zeilberger, zeilberg@math.rutgers.edu`): lprint(``): print(`Please report bugs to zeilberg@math.rutgers.edu`): lprint(``): print(`The most current version of this package and paper`): print(` are available from`): print(`http://www.math.rutgers.edu/~zeilberg/`): print(`For a list of the procedures type ezra();, for help with`): print(`a specific procedure, type ezra(procedure_name);`): print(``): ezra:=proc() if args=NULL then print(`Contains the following procedures: Aijr, CommEv, CommInv, REij`): fi: if nops([args])=1 and op(1,[args])=Aijr then print(`Aijr(i,j,r,Alph): The sum of the weights of words in`): print(` the alphabet Alph that start with i, end with j, and have`): print(`lentgh r `): print(`For example, try: Aijr(1,1,1,{1}); and `): print(`Aijr(1,2,3,{1,2,3}); `): fi: if nops([args])=1 and op(1,[args])=CommEv then print(`CommEv(REX,V,a): commutative evaluation of a regular expression`): print(`in [i,j]'s`): fi: if nops([args])=1 and op(1,[args])=CommInv then print(`CommInv(a,n): The inverse of the matrix I-(a[i,j]), when the a[i,j]`): print(`commute, using the regular expressions`): print(`For example, try CommInv(a,2)`): fi: if nops([args])=1 and op(1,[args])=REij then print(`REij(i,j,Alph,V): A regular expression describing `): print(`words in the alphabet Alph that start at i and end in j`): print(` V denots (*). For example, try: `): print(` REij(1,1,{1,2},V); `): fi: end: Aijr:=proc(i,j,r,Alph) local gu,k,i1,k1,lu: if {i,j} intersect Alph<>{i,j} then RETURN({}): fi: if r=0 then if i=j then RETURN({[]}): else RETURN({}): fi: fi: gu:={}: for k1 from 1 to nops(Alph) do k:=op(k1,Alph): lu:=Aijr(k,j,r-1,Alph): gu:=gu union {seq([[i,k],op(lu[i1])],i1=1..nops(lu))}: od: gu: end: #REij(i,j,Alph,V): A regular expression describing #words in the alphabet Alph that start at i and end in j #V denots (*). For example, try: #REij(1,1,{1,2},V); REij:=proc(i,j,Alph,V) local gu,k,lu,Alph1,i1,k1,m,m1,gu1: if {i,j} intersect Alph<>{i,j} then RETURN({}): fi: if i=j and Alph={i} then RETURN({V({[i,i]})}): fi: Alph1:=Alph minus {i}: gu:={}: for m1 from 1 to nops(Alph1) do for k1 from 1 to nops(Alph1) do m:=Alph1[m1]: k:=Alph1[k1]: lu:=REij(m,k,Alph1,V): gu:=gu union {seq([[i,m],lu[i1],[k,i]],i1=1..nops(lu))}: od: od: gu:={ [V({[i,i]}), V({[gu,V({[i,i]})]}) ]}: if i=j then RETURN(gu): fi: gu1:={}: for k1 from 1 to nops(Alph1) do k:=Alph1[k1]: lu:=REij(k,j,Alph1,V): gu1:=gu1 union {seq([[i,k],lu[i1]],i1=1..nops(lu))}: od: {[gu,gu1]}: end: #CommEv(REX,V,a): commutative evaluation of a regular expression #in [i,j]'s CommEv:=proc(REX,V,a) local i,gu: if type(REX,list) and nops(REX)=2 and type(REX[1],integer) and type(REX[2],integer) then RETURN(a[op(REX)]): fi: if type(REX,list) then gu:=1: for i from 1 to nops(REX) do gu:=gu*CommEv(REX[i],V,a): od: RETURN(normal(gu)): fi: if type(REX,set) then gu:=0: for i from 1 to nops(REX) do gu:=gu+CommEv(REX[i],V,a): od: RETURN(normal(gu)): fi: if type(REX,function) then RETURN(normal(1/(1-CommEv(op(1,REX),V,a)))): fi: ERROR(`Something is wrong`): end: #CommInv(a,n): The inverse of the matrix I-(a[i,j]), when the a[i,j] #commute, using the regular expressions CommInv:=proc(a,n) local A,i,j,V,Alph: Alph:={seq(i,i=1..n)}: for i from 1 to n do for j from 1 to n do A[i,j]:=CommEv(REij(i,j,Alph,V),V,a) od: od: [seq([seq(A[i,j],j=1..n)],i=1..n)]: end: #SimpInv(a,n): The usual of the matrix I-(a[i,j]), when the a[i,j] #commute, using the regular expressions SimpInv:=proc(a,n) local B,C,i,j: with(linalg): B:=matrix(n,n): for i from 1 to n do for j from 1 to n do B[i,j]:=-a[i,j]: od: od: for i from 1 to n do B[i,i]:=1+B[i,i]: od: C:=inverse(B): [seq([seq(C[i,j],j=1..n)],i=1..n)]: end: