print(`Version of Nov. 22, 1996`):
lprint(``):
 
print(`This is DIKDUK,  a Maple package that empirically finds`):
print(`the grammar of combinatorial objects, suitably encoded as words.`):
print(`DIKDUK means grammar in Hebrew`):
lprint(``):
print(` The most current version is available on WWW at:`):
print(` http://www.math.temple.edu/~zeilberg .`):
lprint(``):
print(`For general help, and a list of the available functions,`):
print(` type "ezra();". For specific help type "ezra(procedure_name)" `):
lprint(``):
 
 
 
ezra:=proc()
 
if args=NULL then
print(` DIKDUK, `):
print(`a Maple package that empirically finds`):
print(`the grammar of combinatorial objects, suitably encoded as words.`):
print(`DIKDUK means grammar in Hebrew`):
lprint(``):
print(`For help with a specific procedure, type "ezra(procedure_name);"`):
lprint(``):
print(`Contains procedures: `):
print(` Dikduk, Safa, gf, gf1 , reduc, Reduc `):
print(` Grammar , SafaAd, CORPUSES `):
fi:
 
 
 
if nops([args])=1 and op(1,[args])=`SafaAd` then
print(`SafaAd(dikduk,r,OREKH), given an r-Markovian grammar, in terms`):
print(`of a list of 6 entries:`):
print(`[Milimktsarot,rTuplemat,rTuplesof,rTuple,A,AlefBet],`):
print(`returns all the words of length <=OREKH, where OREKH>=r`):
fi:
 
 
if nops([args])=1 and op(1,[args])=`Grammar` then
print(`Grammar(safa,r,OREKH) tests whether a language, safa, is r-Markovian`):
print(`by checking whether the r-Markovian grammar, guessed by`):
print(`the subset of length <OREKH indeed generates`):
print(`the language for words up to length OREKH`):
print(`if succesful outputs the grammar, otherwise issues an Error message`):
fi:
 
 
if nops([args])=1 and op(1,[args])=`Reduc` then
print(`Reduc(safa): Given a set of words, safa, outputs the set `):
print(`of reduced forms obtained`):
print(`by contracting aa* to a, followed by the set of all letters that`):
print(`occur as aa.`):
fi:
 
 
if nops([args])=1 and op(1,[args])=`reduc` then
print(`reduc(mila): Given a word, mila, outputs the reduced form obtained`):
print(`by contracting aa* to a, followed by the set of letters that`):
print(`occur as aa.`):
fi:
 
 
 
if nops([args])=1 and op(1,[args])=`gf1` then
print(`gf1(dik,r,t): Given an r-Markovian grammar dik, and a variable t`):
print(` finds the weight`):
print(`enumerator(i.e. generating function) of the whole language`):
print(`where the weight of every word is the product of the weights`):
print(`of the letters, and the weight of each letter is `):
print(`t^(number of elements of the letter) [It is being assumed that`):
print(`the letters themselves are some kinds of sets, derived from`):
print(`combinatorial applications]`):
fi:
 
if nops([args])=1 and op(1,[args])=`gf` then
print(`gf(dik,r,wt): Given an r-Markovian grammar dik, and a wt table wt,`):
print(`indicating the wt of each of the letters, finds the weight`):
print(`enumerator(i.e. generating function) of the whole language`):
fi:
 
 
if nops([args])=1 and op(1,[args])=`Dikduk` then
print(`Dikduk(safa,r): Given a set of words, safa, and  the `):
print(`Markovian-memory parameter r returns a 6-component list:`):
lprint(``):
print(`The first is the set if all words of length<r and words`):
print(`of length r that are terminal`):
print(`The second is the set of allowed initial r-tuples of letters`):
print(`The third is the set of allowed final r-tuples of letters`):
print(`The fourth is the set of all r-tuples that show up`):
print(`The fifth is the sequence A[let1,let2,...,letr]:=set of followers,`):
print(` in nature of the pair let1,let2`):
print(`The sixth is the set of letters (just for the record)`):
fi:
 
if nops([args])=1 and op(1,[args])=`Safa` then
print(`Safa(dikduk,r,OREKH), given an r-Markovian grammar, in terms`):
print(`of a list of 6 entries:`):
print(`[Milimktsarot,rTuplemat,rTuplesof,rTuple,A,AlefBet],`):
print(`returns all the words of length OREKH, where OREKH>=r`):
print(`followed by all prefixes of length OREKH`):
fi:
 
 
if nops([args])=1 and op(1,[args])=`CORPUSES` then
print(`CORPUSES(RaLa,N,GVUL): Given a procedure name, RaLa, `):
print(`where RaLa()  generates a`):
print(`random element of a given langauge`):
print(`generates three corpues of that`):
print(`language, the first with N words, the second with 2N `):
print(`words and the third with 3N words, for safety we want N`):
print(` to be at least 10`):
print(`GVUL is a limit to the tries to guarantee that the program`):
print(`terminates`):
print(`If it fails, it returns 0`):
fi:
end:
 
 
 
 
#Dikduk(safa,r): Given a set of words of all lengths,
#safa, and  the Markovian-memory parameter r
#returns a 6-component list:
#The first is the set if all words of length<r
#and the set of words of length r that are terminal
#The second is the set of allowed initial r-tuples of letters
#The third is the set of allowed final r-tuples of letters
#The fourth is the set of all r-tuples that show up
#The fifth is the sequence A[let1,let2,...,letr]:=set of followers, in nature
#of the pair let1,let2
#The sixth is the set of letters (just for the record)
 
Dikduk:=proc(safa,r)
local i,j,mila,rTuplemat,rTuple,A,rTuplesof,AlefBet,
Milimktsarot:
 
rTuplemat:={}:
rTuplesof:={}:
rTuple:={}:
AlefBet:={}:
Milimktsarot:={}:
 
for i from 1 to nops(safa) do
mila:=op(i,safa):
 
if nops(mila)<r then
Milimktsarot:=Milimktsarot union {mila}:
AlefBet:=AlefBet union convert(mila,set):
 
 elif nops(mila)>=r then
   AlefBet:=AlefBet union convert(mila,set):
   rTuplemat:=rTuplemat union {[op(1..r,mila)]}:
   rTuplesof:=rTuplesof union {[op(nops(mila)-r+1..nops(mila),mila)]}:
 
 for j from 1 to nops(mila)-r+1 do
   rTuple:=rTuple union {[op(j..j+r-1,mila)]}:
 od:
 
fi:
 
od:
 
 
 
for i from 1 to nops(rTuple) do
A[op(op(i,rTuple))]:={}:
od:
 
for i from 1 to nops(safa) do
mila:=op(i,safa):
 
if nops(mila)>r then
for j from 1 to nops(mila)-r do
A[op(j..j+r-1,mila)]:= A[op(j..j+r-1,mila)] union {op(j+r,mila)}:
od:
fi:
od:
   
[Milimktsarot,rTuplemat,rTuplesof,rTuple,A,AlefBet]:
end:
 
 
 
#SafaAd(dikduk,r,OREKH), given an r-Markovian grammar, in terms
#of a list of 6 entries:
#[Milimktsarot,rTuplemat,rTuplesof,rTuple,A,AlefBet],
#returns all the words of length <=OREKH, where OREKH>=r
 
SafaAd:=proc(dikduk,r,OREKH)
local lu,i:
lu:=dikduk[1]:
 
for i from r to  OREKH do
lu:=lu union Safa(dikduk,r,i)[1]:
od:
 
lu:
end:
 
 
 
#Safa(dikduk,r,OREKH), given an r-Markovian grammar, in terms
#of a list of 6 entries:
#[Milimktsarot,rTuplemat,rTuplesof,rTuple,A,AlefBet],
#returns all the words of length OREKH, where OREKH>=r
#followed by all prefixes of length OREKH
 
Safa:=proc(dikduk,r,OREKH)
local rTuplemat,rTuplesof,A,gu,gu1,gu2,mila,Mutar,i,j:
option remember:
 
if OREKH<r then
ERROR(`r>=OREKH`):
fi:
 
rTuplemat:=op(2,dikduk):
 
rTuplesof:=op(3,dikduk):
 
A:=op(5,dikduk):
 
if r=OREKH then
RETURN(rTuplemat intersect rTuplesof,rTuplemat):
fi:
 
gu:=Safa(dikduk,r,OREKH-1)[2]:
 
gu1:={}:
gu2:={}:
 
for i from 1 to nops(gu) do
mila:=op(i,gu):
Mutar:=A[op(nops(mila)-r+1..nops(mila),mila)]:
 
for j from 1 to nops(Mutar) do
gu2:=gu2 union {[op(mila),op(j,Mutar)]}:
 
if member( [op(nops(mila)-r+2..nops(mila),mila),op(j,Mutar)],rTuplesof) then
   gu1:=gu1 union {[op(mila),op(j,Mutar)]}:
fi:
od:
od:
gu1,gu2:
end:
 
 
#gf(dik,r,wt): Given an r-Markovian grammar dik, and a wt table wt,
#indicating the wt of each of the letters, finds the weight
#enumerator(i.e. generating function) of the whole language
 
gf:=proc(dik,r,wt)
local ktsarot,mu,mish,eq,var,i,KULAM,INI,FIN,A,B,lu,eq1,mutarim,mila,ot1,j:
 
mish:=proc(mila,wt)
local i,gu:
 
gu:=1:
for i from 1 to nops(mila) do
gu:=gu*wt[op(i,mila)]:
od:
gu:
end:
 
 
ktsarot:=dik[1]:
 
INI:=dik[2]:
FIN:=dik[3]:
KULAM:=dik[4]:
A:=dik[5]:
 
mu:=0:
 
for i from 1 to nops(ktsarot) do
mila:=op(i,ktsarot):
 
if nops(mila)<r then
mu:=mu+mish(mila,wt):
fi:
od:
 
 
eq:={}:
var:={}:
 
for i from 1 to nops(KULAM) do
mila:=op(i,KULAM):
var:=var union {B[op(mila)]}:
 
if member(mila,FIN) then
 
 lu:=mish(mila,wt):
else
lu:=0:
fi:
 
eq1:=B[op(mila)]-lu:
mutarim:=A[op(mila)]:
 
for j from 1 to nops(mutarim) do
ot1:=op(j,mutarim):
eq1:=eq1 - wt[op(1,mila)]*B[op(2..nops(mila),mila),ot1]:
od:
eq:=eq union {eq1}:
od:
 
 
var:=solve(eq,var):
 
for i from 1 to nops(INI) do
mila:=op(i,INI):
 
mu:=mu+subs(var,B[op(mila)]):
od:
normal(mu):
end:
 
 
 
 
 
gf1:=proc(dik,r,t)
local ktsarot,mu,mish1,eq,var,i,KULAM,INI,FIN,A,B,lu,eq1,mutarim,mila,ot1,j:
 
mish1:=proc(mila,t)
local i,gu:
 
gu:=1:
for i from 1 to nops(mila) do
gu:=gu*t^nops(op(i,mila)):
od:
gu:
end:
 
 
ktsarot:=dik[1]:
 
INI:=dik[2]:
FIN:=dik[3]:
KULAM:=dik[4]:
A:=dik[5]:
 
mu:=0:
 
for i from 1 to nops(ktsarot) do
mila:=op(i,ktsarot):
if nops(mila)<r then
mu:=mu+mish1(mila,t):
fi:
od:
 
 
eq:={}:
var:={}:
 
for i from 1 to nops(KULAM) do
mila:=op(i,KULAM):
var:=var union {B[op(mila)]}:
 
lu:=0:
if member(mila,FIN) then
 lu:=mish1(mila,t):
fi:
 
 
eq1:=B[op(mila)]-lu:
mutarim:=A[op(mila)]:
 
for j from 1 to nops(mutarim) do
ot1:=op(j,mutarim):
eq1:=eq1 - t^nops(op(1,mila))*B[op(2..nops(mila),mila),ot1]:
od:
eq:=eq union {eq1}:
od:
 
 
var:=solve(eq,var):
 
for i from 1 to nops(INI) do
mila:=op(i,INI):
 
mu:=mu+subs(var,B[op(mila)]):
od:
normal(mu):
end:
 
 
 
#reduc(mila): Given a word, mila, outputs the reduced form obtained
#by contracting aa* to a, followed by the set of letters that
#occur as aa
 
reduc:=proc(mila)
local i,mila1,gu,ot1:
 
if mila=[] then
 RETURN([],{}):
fi:
 
gu:={}:
 
mila1:=[op(1,mila)]:
 
for i from 2 to nops(mila) do
ot1:=op(i,mila):
 
if ot1=op(nops(mila1),mila1) then
 gu:=gu union {ot1}:
else
 mila1:=[op(mila1),ot1]:
fi:
 
od:
mila1,gu:
end:
 
 
 
 
 
#Reduc(safa): Given a set of words, safa, outputs the set 
#of reduced forms obtained
#by contracting aa* to a, followed by the set of all letters that
#occur as aa
 
Reduc:=proc(safa)
local i,safa1,gu,mila,rodi:
 
safa1:={}:
gu:={}:
 
for i from 1 to nops(safa) do
 mila:=op(i,safa): 
 rodi:=reduc(mila):
 safa1:=safa1 union {rodi[1]}:
 gu:=gu union rodi[2]:
od:
 
safa1,gu:
end:
 
 
 
#Grammar(safa,r,OREKH) tests whether a language, safa, is r-Markovian
#by checking whether the r-Markovian grammar, guessed by
#the subset of length <OREKH indeed generates
#the language for words up to length OREKH
#if succesful outputs the grammar, otherwise issues an Error message
 
Grammar:=proc(safa,r,OREKH)
local i,di,lashon,mila,sa1,sa2:
 
if  not r<OREKH then
ERROR(`OREKH>r`):
fi:
 
sa1:={}:
sa2:={}:
 
for i from 1 to nops(safa) do
mila:=op(i,safa):
 
if nops(mila)<OREKH then
 sa1:=sa1 union {mila}:
elif nops(mila)=OREKH then
 sa2:=sa2 union {mila}:
fi:
 
od:
 
di:=Dikduk(sa1,r):
 
 
lashon:=Safa(di,r,OREKH)[1]:
 
#print(`sa2 minus lashon is`, sa2 minus lashon):
#print(`lashon minus sa2 is`, lashon minus sa2):
if lashon<>sa2 then
print(`Could not guess a grammar, try to raise r or  generate longer words`):
RETURN(0):
fi:
 
di:
end:
 
savim:=proc(dik1,dik2)
local i:
for i from 1 to 4 do
if dik1[i]<>dik2[i] then
 RETURN(0):
fi:
od:
 
if dik1[6]<>dik2[6] then
 RETURN(0):
fi:
 
 
if op(op(op(dik1[5])))<>op(op(op(dik1[5]))) then
 RETURN(0):
fi:
 
1:
end:
 
 
 
#CORPUSES(RaLa,N,GVUL): Given a procedure name, RaLa, 
#where RaLa()  generates a
#random element of a given langauge
#generates three corpues of that
#language, the first with N words, the second with 2N words and the third
#with 3N words, for safety we want N to be at least 10
#GVUL is a limit to the tries to guarantee that the program
#terminates
#If it fails, it returns 0
 
CORPUSES:=proc(RaLa,N,GVUL)
local i,sa1,sa2,sa3,mila:
 
if not type(N,integer) or N<10 then
ERROR(`N must be an integer>=10`):
fi:
 
sa:={}:
 
for i from 1 to GVUL while nops(sa)<N do
mila:=RaLa():
if not member(mila,sa) then
 sa:=sa union {mila}:
fi:
od:
 
sa1:=sa:
 
if nops(sa1)<N then
print(`In Corpuses, could not get enough words for the first corpus`):
print(`Try to raise the second argument, GVUL`):
RETURN(0):
fi:
 
 
for i from 1 to GVUL while nops(sa)<2*N do
mila:=RaLa():
if not member(mila,sa) then
 sa:=sa union {mila}:
fi:
od:
sa2:=sa:
 
 
 
if nops(sa2)<2*N then
print(`In Corpuses, could not get enough words for the second corpus`):
print(`Try to raise the second argument, GVUL`):
RETURN(0):
fi:
 
 
 
 
for i from 1 to GVUL while nops(sa)<3*N do
mila:=RaLa():
if not member(mila,sa) then
 sa:=sa union {mila}:
fi:
od:
sa3:=sa:
 
if nops(sa3)<3*N then
print(`In Corpuses, could not get enough words for the third corpus`):
print(`Try to raise the second argument, GVUL`):
RETURN(0):
fi:
 
sa1,sa2,sa3:
 
end: