# 
# Noam
# Anne E. Edlin
# Opening Documentation
  print(`Noam`):
  print(`A Maple package for handling `):
  print(`Formal Grammars and Formal Languages.`):
  print(`Based on the book Introduction to Formal Languages`):
  print(`written by Gyorgy E. Revesz.`):
  print(`This Package was written by Anne E. Edlin`):
  print(`With thanks to Dr Zeilberger's class, Math 574.`):
  print(`Version-11th Sept 1997.`):
  print(`For a list of procedures type Help.`):
  print(`For help on a specific topic type Help(procedure).`):
  print(` `):
  print(` `):

  
# Help procedure
  Help:=proc()
  local G;
  if args=NULL then 
    print(`Contains procedures`):
    print(`onestep,nstep,nstept,nstepnt,lang,langt,langnt`):
    print(`isGrammar,isGrammar3,isGrammar2,isGrammar1,Type`):
    print(`catG, unionG, iterateG,termG`):
    print(`and a Library of Grammars called lib.`):
    print(`All references refer to the book`):
    print(`Introduction to Formal Languages`):
    print(`by Gyorgy E. Revesz.`):
  elif nargs=1 and args[1]=isGrammar then 
    print(`Inputs a candidate for a formal grammar.`):
    print(`Outputs 0 if the input grammar is not`): 
    print(`in the correct form for this package`): 
    print(`and gives information on what needs changing.`):
    print(`Outputs 1 if it is grammatically correct.`):
    print(`This is an implementation of Definition 1.1`):
    print(`e.g G1:=`):
    print(G1):
    print(`isGrammar(G1);`):
    isGrammar(G1):
  elif nargs=1 and args[1]=onestep then 
    print(`Inputs a grammar and a word.`):
    print(`Outputs all the words`):
    print(`derivable from the given word in one step`):
    print(`under the input grammar.`):
    print(`This is an implementation of Definition 1.2`):
    print(`e.g.  onestep(G1,B);`):
    onestep(G1,B):
  elif nargs=1 and args[1]=nstep then 
    print(`Inputs a grammar, a word and a positive integer.`):
    print(`Outputs all words derivable from the word`);
    print(`in at most n steps.`):
    print(`This is an implementation of Definition 1.3`):
    print(`e.g. nstep(G5,[b,B],4)`):
    nstep(G5,[b,B],4):
  elif nargs=1 and args[1]=nstept then 
    print(`Inputs a grammar, a word and a positive integer.`):
    print(`Outputs all terminal words derivable from the word`):
    print(`in n steps.`):
    print(`e.g. nstept(G6,[a,B],5)`):
    nstept(G6,[a,B],5):
  elif nargs=1 and args[1]=nstepnt then 
    print(`Inputs a grammar, a word and a positive integer.`):
    print(`Outputs all non-terminal words derivable from the word`);
    print(`in n steps.`):
    print(`e.g. nstepnt(G7,[B,b,b],2)`):
    nstepnt(G7,[B,b,b],2):
  elif nargs=1 and args[1]=lang then 
    print(`Inputs a grammar and a positive integer.`):
    print(`Outputs all words derivable in at most n steps,`):
    print(`under the input grammar`):
    print(`e.g. lang(G12,2);`):
    lang(G12,2):
  elif nargs=1 and args[1]=langt then 
    print(`Inputs a grammar and a positive integer.`):
    print(`Outputs all terminal words derivable`):
    print(`in at most n steps,`):
    print(`under the input grammar`):
    print(`e.g. langt(G8,5);`):
    langt(G8,5):
  elif nargs=1 and args[1]=langnt then 
    print(`Inputs a grammar and a positive integer.`):
    print(`Outputs all non-terminal words derivable`):
    print(`in at most n steps,`):
    print(`under the input grammar`):
    print(`e.g. langnt(G11,2);`):
    langnt(G11,2):
  elif nargs=1 and args[1]=isGrammar3 then 
    print(`Checks to see if the input grammar is of type 3.`):
    print(`e.g. isGrammar3(G14);`):
    isGrammar3(G14):print(`0`):
    print(`e.g. isGrammar3(G15);`):
    isGrammar3(G15):
  elif nargs=1 and args[1]=isGrammar2 then 
    print(`Checks to see if the input grammar is of type 2.`):
    print(`e.g. isGrammar2(G14);`):
    isGrammar2(G14):
  elif nargs=1 and args[1]=isGrammar1 then 
    print(`Checks to see if the input grammar is of type 1.`):
    print(`e.g. isGrammar1(G11);`):
    isGrammar1(G11):
  elif nargs=1 and args[1]=Type then 
    print(`Identifies the type of the input grammar.`):
    print(`This is an implementaion of Definition 1.6`):    
    print(`e.g. Type(G6);`):
    Type(G6):
  elif nargs=1 and args[1]=lib then 
    print(`Provides a number of predefined grammars and`):
    print(`information on them.`):
    print(`For help on a specific grammar type lib(grammar name)`):
    print(`e.g lib(G2);`):
    lib(G2):
  elif nargs=1 and args[1]=catG then
    print(`Produces the catenation of two input grammars,`):
    print(`using input indeterminates.`):
    print(`This is an implementation of part of Theorem 2.2`):
    print(`eg. catG(G1,G2,X,Z);`):
    catG(G1,G2,X,Z);
  elif nargs=1 and args[1]=unionG then
    print(`Produces the union of two input grammars,`):
    print(`using input indeterminates.`):
    print(`This is an implementation of part of Theorem 2.2`):
    print(`eg. unionG(G5,G7,X,Z);`):
    unionG(G5,G7,X,Z);
  elif nargs=1 and args[1]=iterateG then
    print(`Produces the iteration grammar for the input grammar,`):
    print(` using the input indeterminate.`):
    print(`This is an implementation of part of Theorem 2.2`):
    print(`eg. G:=iterateG(G2,Z);`);G:=iterateG(G2,Z):
    print(iterateG(G2,Z));
    print(`langt(G2,5);`);
    print(langt(G2,5));
    print(`langt(G,7);`);
    print(langt(G,7));
  elif nargs=1 and args[1]=termG then
    print(`Removes all terminal letters`):
    print(`from the left hand side of the rules.`):
    print(`This is an implementation of Theorem 2.1`):
    print(`eg. termG(G2,D);`):
    print(termG(G2,D)):
  else print(`There is no help available on`, args):
  fi:
  end:



# Forming languages from grammars
# This procedure finds all words derivable from the input word in one
# step under  the input grammar G.
  onestep:=proc(G,w)
  local i,j,k,VN,VT,F,ma,setf,seg,ru,P,Q,neww:
  option remember:
  if isGrammar(G)=0 then
    ERROR(`Your input`,G,`is not a grammar.`):
  fi:
  VN:=op(1,G):
  VT:=op(2,G):
  F:=op(4,G):
  if ({op(w)} intersect (VN union VT)) <>  {op(w)}  then
    ERROR(`The input word must be made up of letters from the first and second components of the input grammar.`): 
  fi:
  ma:=MaxP(F):
  setf:={}:
  for i from 1 to nops(w) do
    for j from i to min(i+ma-1,nops(w)) do
    seg:=[op(i..j,w)]:
      for k from 1 to nops(F) do
        ru:=op(k,F):
        P:=op(1,ru):
        Q:=op(2,ru):
        if seg=P then
          neww:=[op(1..i-1,w),op(Q),op(j+1..nops(w),w)]:
          setf:=setf union {neww}:
        fi:
      od:
    od:
  od:
  setf:
  end:
# This procedure finds the maximum length of the left hand side of the
# elements in the set of rewriting rules.
  MaxP:=proc(F)
  local i,P,ma:
  option remember:
  ma:=0:
  for i from 1 to nops(F) do
  P:=op(1,op(i,F)):
  if nops(P)>ma then 
    ma:=nops(P):
  fi:
  od:
  ma:
  end:
# This procedure gives all words derivable from the input word under G
# in at most n steps.  It gives its output as a list of sets.
# The first component is the terminal words, the second the nonterminal
# words.
  nstep1:=proc(G,w,n)
  local bset,i,j,k,l,tset,ntset,aset:
  option remember:
  ntset:={w}:
  tset:={}:
  aset:={}:
  for i from 1 to n do
    for j from 1 to nops(ntset) do
      aset:=onestep(G,op(j,ntset)):
      for k from 1 to nops(aset) do
        bset:={}:
        for l from 1 to nops(op(k,aset)) do
          bset:= bset union {op(l,op(k,aset))}:
        od:
        if (bset intersect op(1,G))= {} then
            tset:=tset union {op(k,aset)}:
        else
            ntset:=ntset union {op(k,aset)}:
        fi:
      od: 
    od:
  od:
  [tset,ntset]
  end:
# This procedure gives all words derivable from G in at most n steps.
  lang:=proc(G,n)
  local S,L:
  S:=op(3,G):
  L:=nstep1(G,[S],n):
  op(1,L) union op(2,L):
  end:
# This procedure gives all words derivable from w in at most n steps
# under G.
  nstep:=proc(G,w,n)
  local L:
  L:=nstep1(G,w,n):
  op(1,L) union op(2,L):
  end:
# This procedure gives all terminal words derivable from G in at most n
# steps.
  langt:=proc(G,n)
  local S,L:
  S:=op(3,G):
  L:=nstep1(G,[S],n):
  op(1,L):
  end:
# This procedure gives all terminal words derivable from w in at most n
# steps under G.
  nstept:=proc(G,w,n)
  local L:
  L:=nstep1(G,w,n):
  op(1,L):
  end:
# This procedure gives all nonterminal words derivable from G in at most
#  n steps.
  langnt:=proc(G,n)
  local S,L:
  S:=op(3,G):
  L:=nstep1(G,[S],n):
  op(2,L):
  end:
# This procedure gives all nonterminal words derivable from w in at most
# n steps under G.
  nstepnt:=proc(G,w,n)
  local L: 
  L:=nstep1(G,w,n):
  op(2,L):
  end:  
  
  

    
# Library of grammars
  lib:=proc():
  if args=NULL then 
    print(`Contains languages `):
    print(`G1,G2,G3,G4,G5,G6,G7,G8,G9,G10,G11,G12,G13,G14.`):
    print(`To obtain information about a specific grammar type lib(grammar name)`):
    print(`To obtain a list of the grammars available type lib(all)`):
  elif nargs=1 and args[1]=all then
    print(`G1=`):print(G1):print(``):
    print(`G2=`):print(G2):print(``):
    print(`G3=`):print(G3):print(``):
    print(`G4=`):print(G4):print(``):
    print(`G5=`):print(G5):print(``):
    print(`G6=`):print(G6):print(``):
    print(`G7=`):print(G7):print(``):
    print(`G8=`):print(G8):print(``):
    print(`G9=`):print(G9):print(``):
    print(`G10=`):print(G10):print(``):
    print(`G11=`):print(G11):print(``):
    print(`G12=`):print(G12):print(``):
    print(`G13=`):print(G13):print(``):
    print(`G14=`):print(G14):print(``):
    print(`G15=`):print(G15):print(``):
  elif nargs=1 and args[1]=G1 then
    print(`G1 generates all words with the same number of a's and b's.`):
    print(G1):
  elif nargs=1 and args[1]=G2 then
    print(`G2 generates all words of the form a^n b^n c^n, for n=1,2,...`):
    print(G2):
  elif nargs=1 and args[1]=G3 then
    print(`G3 generates real English sentences`):
    print(G3):
  elif nargs=1 and args[1]=G4 then
    print(`G4 generates all words of the form a^i b^i for i=0,1,...`):
    print(G4):
  elif nargs=1 and args[1]=G5 then
    print(`G5 generates all words of the form a^i b^j where i=0,1,... and j =i`):
    print(G5):
  elif nargs=1 and args[1]=G6 then 
    print (`G6 generates all words of the form a^i b^j a^j b^i where i,j=0,1,...`):
    print(G6):
  elif nargs=1 and args[1]=G7 then
    print(`G7 generates the language of words of the form a^i b^i a^j b^j with i=0,1,... j=0,1,...`):
    print(G7):
  elif nargs=1 and args[1]=G8 then
    print(`G8 generates all words of the form a^i b^i for i=0,1,... `):
    print(`and all words of the form b^j a^j for j=0,1,...`):
    print(G8):
  elif nargs=1 and args[1]=G9 then
    print(`G9 generates palindromes made up of the letters a and b`):
  elif nargs=1 and args[1]=G10 then
    print(`G10 generates words of the form a^i b^j c^(i+j) for i,j=0,1,2,...`):
  elif nargs=1 and args[1]=G11 then
    print(`G11 generates all words containing equal numbers of a's and b's`):
  elif nargs=1 and args[1]=G12 then
    print(`G12 generates the empty language.`):
  elif nargs=1 and args[1]=G13 then
    print(`G13 generates all words of the form a^(n^2)`):
  elif nargs=1 and args[1]=G14 then
    print(`G14 generates all word of the form a b^n c^m d, for m,n =0`):
  elif nargs=1 and args[1]=G15 then
    print(`G15 generates all word of the form a b^n c^m d, for m,n =0`):
  else print(`The library contains no such grammar`):
  fi:
  end:
G1:=[{S,A,B},{a,b},S,{[[S],[a,B]],[[S],[b,A]],[[A],[a]],[[A],[a,S]],[[A],[b,A,A]],[[B],[b]],[[B],[b,S]],[[B],[a,B,B]]}]:
G2:=[{S,X,Y},{a,b,c},S,{[[S],[a,b,c]],[[S],[a,X,b,c]],[[X,b],[b,X]],[[X,c],[Y,b,c,c]],[[b,Y],[Y,b]],[[a,Y],[a,a,X]],[[a,Y],[a,a]]}]:
G3:=[{S,A,B,C,D,E,F,G},{the,mathematical,tall,boy,question,quickly,answered},S,{[[S],[A,B]],[[A],[C,D,E]],[[B],[G,B]],[[B],[F,A]],[[C],[the]],[[D],[mathematical]],[[D],[tall]],[[E],[boy]],[[E],[question]],[[G],[quickly]],[[F],[answered]]}]:
G4:=[{S},{a,b},S,{[[S],[]],[[S],[a,S,b]]}]:
G5:=[{S,B},{a,b},S,{[[S],[]],[[S],[a,S,b]],[[S],[B]],[[B],[B,b]],[[B],[]]}]:
G6:=[{S,B},{a,b},S,{[[S],[]],[[S],[a,S,b]],[[S],[B]],[[B],[b,B,a]],[[B],[]]}]:
G7:=[{S,B},{a,b},S,{[[S],[]],[[S],[B,B]],[[S],[B]],[[B],[a,B,b]],[[B],[]]}]:
G8:=[{S,A,B},{a,b},S,{[[S],[A]],[[S],[B]],[[A],[a,A,b]],[[B],[b,B,a]],[[A],[]],[[B],[]]}]:
G9:=[{S},{a,b},S,{[[S],[]],[[S],[a,S,a]],[[S],[b,S,b]]}]:
G10:=[{S,B},{a,b,c},S,{[[S],[]],[[S],[a,S,c]],[[S],[B]],[[B],[b,B,c]],[[B],[]]}]:
G11:=[{S},{a,b},S,{[[S],[a,b]],[[S],[b,a]],[[S],[S,S]],[[S],[a,S,b]],[[S],[b,S,a]]}]:
G12:=[{A,B,S},{a,b},S,{[[S],[a,A,B]],[[b,B],[a]],[[A,b],[S,B,b]],[[A,a],[S,a,B]],[[B],[S,A]],[[B],[a,b]]}]:
G13:=[{S,A,B,C,D,E},{a},S,{[[S],[a]],[[S],[C,D]],[[C],[A,C,B]],[[C],[A,B]],[[A,B],[a,B,A]],[[A,a],[a,A]],[[B,a],[a,B]],[[A,D],[D,a]],[[B,D],[E,a]],[[B,E],[E,a]],[[E],[a]]}]: G14:=[{S,A,B},{a,b,c,d},S,{[[S],[A,B]],[[A],[A,b]],[[A],[a]],[[B],[c,B]],[[B],[d]]}]:
G15:=[{S,C,D},{a,b,c,d},S,{[[S],[a,C]],[[C],[b,C]],[[C],[D]],[[D],[c,D]],[[D],[d]]}]:

# This procedure removes all terminal letters from the left hand side of
# the rules
  termG:=proc(G,X)
  local VN,VT,i,VTl,S,F1,F,VN1,G1:
  VN:=op(1,G):
  if member(X,convert(VN,set)) then 
    ERROR(`The second input can not be a member of the first set of the input grammar.`):
  fi:
  VT:=op(2,G):
  VTl:=convert(VT,list):
  G1[0]:=G:
  F1:={}:
  VN1:={}:
  for i from 1 to nops(VTl) do
    G1[i]:=subs({op(i,VTl)=X[i]},G1[i-1]):
    F1:=F1 union {[[X[i]],[op(i,VTl)]]}:
    VN1:=VN1 union {X[i]}:
  od:
  G1:=G1[nops(VTl)]:
  VN:=VN union VN1:
  S:=op(3,G1):
  F:=op(4,G1) union F1:
  [VN,VT,S,F]:
  end:



# Regular operations on languages
# This procedure performs the union of two input grammars.
  unionG:=proc(G1,G2,X,Y)
  local VN1,VN2,VT1,VT2,F1,F2,VN0,VT0,F0,g11,g22,g10,g20, g12,
  g21,i,j,VN21,VN11 :
  VN11:=op(1,G1):
  if member(X,convert(VN11,set)) then 
    ERROR(`The third input can not be a member of the first set of G1`):
  fi:
  g11[1]:=subs({op(1,VN11)=X[1]},G1):
  for i from 2 to nops(VN11) do
   g11[i]:=subs({op(i,VN11)=X[i]},g11[i-1]):
  od:
  g12:=g11[nops(VN11)]:
  VN21:=op(1,G2):
  if member(Y,convert(VN21,set)) then 
    ERROR(`The fourth input can not be a member of the first set of G2`):
  fi:
  g21[1]:=subs({op(1,VN21)=Y[1]},G2);
  for j from 2 to nops(VN21) do
   g21[j]:=subs({op(j,VN21)=Y[j]},g21[j-1]);
  od:
  g22:=g21[nops(VN21)]:
  g10:=subs({op(3,g12)=S1},g12);
  g20:=subs({op(3,g22)=S2},g22);
  VN1:=op(1,g10):
  VT1:=op(2,g10):
  F1:=op(4,g10):
  VN2:=op(1,g20):
  VT2:=op(2,g20):
  F2:=op(4,g20):
  VN0:=VN1 union VN2 union {S0}:
  VT0:=VT1 union VT2:
  F0:=F1 union F2 union {[[S0],[S1]],[[S0],[S2]]}:
  [VN0, VT0, S0, F0];
  end:
# This procedure performs the catenation of two input grammars.
  catG := proc(G1,G2,X,Y) 
  local VN1,VN2,VT1,VT2,F1,F2,VN0,VT0,F0,g11,g22,g10,g20, g12,
  g21,i,j,VN21,VN11 :
  VN11:=op(1,G1):
  if member(X,convert(VN11,set)) then 
    ERROR(`The third input can not be a member of the first set of G1`):
  fi:
  g11[1]:=subs({op(1,VN11)=X[1]},G1):
  for i from 2 to nops(VN11) do
   g11[i]:=subs({op(i,VN11)=X[i]},g11[i-1]):
  od:
  g12:=g11[nops(VN11)]:
  VN21:=op(1,G2):
  if member(Y,convert(VN21,set)) then 
    ERROR(`The fourth input can not be a member of the first set of G2`):
  fi:
  g21[1]:=subs({op(1,VN21)=Y[1]},G2);
  for j from 2 to nops(VN21) do
   g21[j]:=subs({op(j,VN21)=Y[j]},g21[j-1]);
  od:
  g22:=g21[nops(VN21)]:
  g10:=subs({op(3,g12)=S1},g12);
  g20:=subs({op(3,g22)=S2},g22);
  VN1:=op(1,g10):
  VT1:=op(2,g10):
  F1:=op(4,g10):
  VN2:=op(1,g20):
  VT2:=op(2,g20):
  F2:=op(4,g20):
  VN0:=VN1 union VN2 union {S0}:
  VT0:=VT1 union VT2:
  F0:=F1 union F2 union {[[S0],[S1,S2]]}:
  [VN0, VT0, S0, F0];
  end:
# This procedure forms the iteration of an input grammar.
  iterateG := proc(G1,X) 
  local VN1,F1,VN0,VT0,F0,g11,g10,i,VN11,g12 :
  VN11:=op(1,G1):
  if member(X,convert(VN11,set)) then 
    ERROR(`The second input can not be a member of the first set of G1`):
  fi:
  g11[1]:=subs({op(1,VN11)=X[1]},G1):
  for i from 2 to nops(VN11) do
   g11[i]:=subs({op(i,VN11)=X[i]},g11[i-1]):
  od:
  g12:=g11[nops(VN11)]:
  g10:=subs({op(3,g12)=S1},g12);
  VN1:=op(1,g10):
  VT0:=op(2,g10):
  F1:=op(4,g10):
  VN0:=VN1 union {S0}:
  F0:=F1 union {[[S0],[S1,S0]],[[S0],[]]}:
  [VN0, VT0, S0, F0];
  end:
  
  



  
# Checking input grammars and their type
# This procedure verifies that the input grammar is in the correct form
# for use within this package.
  isGrammar:=proc(G)
  local VN,VT,S,F,P,Q,i,ru,LP,LQ:
  if not type(G,list) then 
    print(` A grammar is a list.`):
    RETURN(0):
  fi:
  if nops(G) <>4 then 
    print(`A grammar is made up of 4 elements.`):
    RETURN(0):
  fi:
  VN:=op(1,G):
  VT:=op(2,G):
  S:=op(3,G):
  F:=op(4,G):
  if not type(VN,set) then 
    print(`The first component of a grammar should be a set.`):
    RETURN(0):
  fi:
  if not type(VT,set) then 
    print(`The second component of a grammar should be a set.`):
    RETURN(0):
  fi:
  if not type(F,set)  then 
    print(`The fourth component of a grammar should be a set.`):
    RETURN(0):
  fi:
  if not member(S,VN) then 
    print(`The third component of a grammar should be`):
    print(`an element of the set defined in the first component.`):
    RETURN(0):
  fi:
  if VN intersect VT  <> {} then 
    print(`The first and second components of a grammar`):
    print(`should have no elements in common.`):
    RETURN(0):
  fi:
  for i from 1 to nops(F) do
    ru:=op(i,F):
    if not type(ru,list) or nops(ru) <>2 then 
      print(`The elements in the fourth component should be lists`):
      print(` made up of 2 elements.`):
      RETURN(0):
    fi:
    P:=op(1,ru):
    Q:=op(2,ru):
    if not type(P,list) then 
      print(`The first elements of the lists in component four`):
      print(` should be lists themselves.`):
      RETURN(0):
    fi:
    if not type(Q,list) then 
      print(`The second elements of the lists in component four`):
      print(` should be lists themselves.`):
      RETURN(0):
    fi:
    LP:=convert(P,set):
    LQ:=convert(Q,set):
    if (LP intersect (VN union VT)) <>LP then 
      print(`The inner lists of the fourth component`):
      print(`should be made up of elements from`):
      print(`the first and second components.`):  
      RETURN(0):
    fi:
    if (LQ intersect (VN union VT)) <>LQ then 
      print(`The inner lists of the fourth component`):
      print(` should be made up of elements from`):
      print(`the first and second components.`):
      RETURN(0):
    fi:
    if LP intersect VN={} then 
      print(`The first element within`):
      print(`the inner lists of the fourth component`):
      print(`should contain elements from the first component.`):
      RETURN(0):
    fi:
  od:
  1:
  end:
# This procedure identifies the type of the grammar.
  Type:=proc(G):
  if isGrammar(G)=0 then
    ERROR(`not a grammar`):
  fi:
  if isGrammar3(G)=1 then
    RETURN(3):
  elif isGrammar2(G)=1 then
    RETURN(2):
  elif isGrammar1(G)=1 then
    RETURN(1):
  else RETURN(0):
  fi:
  end:
# This procedure tests whether the input grammar is of type 3 or not.
  isGrammar3:=proc(G)
  local VN,VT,F,i,Q,P,ru,q,QS,q1,q1S:
  if isGrammar(G)=0 then
    print(`This is not a grammar.`):
    RETURN(0):
  fi:
  VT:=op(2,G);
  F:=op(4,G);
  VN:=op(1,G);
  for i from 1 to nops(F) do
    ru:=op(i,F):
    P:=op(1,ru):
    Q:=op(2,ru):
    if nops(P) <>1 then 
       RETURN(0):
    fi:
    if not member(op(1,P),VN) then
      RETURN(0):
    fi:
    q:=op(nops(Q),Q):
    QS:=convert(Q,set):
    q1:=[op(1..nops(Q)-1,Q)]:
    q1S:=convert(q1,set):
      if not (QS intersect VT)=QS then
        if not (member(q,VN) and ((q1S intersect VT)=q1S)) then
          RETURN(0):
        fi:
      fi:
  od:
  1:
  end:
# This procedure tests whether the input grammar is of type 2 or not.
  isGrammar2:=proc(G)
  local VN,F,i,P,ru:
  if isGrammar(G)=0 then
    RETURN(0):
  fi:
  F:=op(4,G);
  VN:=op(1,G);
  for i from 1 to nops(F) do
    ru:=op(i,F):
    P:=op(1,ru):
    if nops(P) <>1 then 
      RETURN(0):
    fi:
    if not member(op(1,P),VN) then
      RETURN(0):
    fi:
  od:
  1:
  end:
# This procedure tests whether the input grammar is of type 1 or not.
  isGrammar1:=proc(G)
  local VN,S,F,i,P,ru,Q,t,j,k,ru1,Q1:
  if isGrammar(G)=0 then
    RETURN(0):
  fi:
  S:=op(3,G);
  F:=op(4,G);
  VN:=op(1,G);
  for i from 1 to nops(F) do
    ru:=op(i,F):
    Q:=op(2,ru):
    P:=op(1,ru):
    if op(P)=S then 
      if nops(Q)=0 then 
        for t from 1 to nops(F) do 
          ru1:=op(t,F):
          Q1:=op(2,ru1):
          if S intersect convert(Q1,set)=S then
            RETURN(0):
          fi:
        od:
      fi:
    fi:
    for j from 1 to nops(P) do
      if member(op(j,P),VN) then
        for k from 1 to j-1 do 
          if op(k,P) <>op(k,Q) then
            RETURN(0):
          fi:
        od:
        for k from 1 to nops(P)-i do
          if op(nops(P)-k,P) <>op(nops(Q)-k,Q) then
            RETURN(0):
          fi:
        od:
      fi:
    od:
  od:
  1:
  end: