#Yusra Naqvi #HW 18 #OK to post ################################################################################ #2 #AllWords(A,n): inputs an alphabet A, and a positive integer n, and #outputs the set of all nops(A)^n words of length n. AllWords:=proc(A,n) local S,i,v: S[0]:={[]}: for i from 1 to n do S[i]:=`union`(seq({seq([A[j], op(v)], v in S[i-1])},j=1..nops(A))): od: S[n]: end: ### #IsBad2(w,fp1,B): returns true iff the word w is equal to a pattern fp1. #It assumes that nops(w)=nops(fp1), which is fine because this is how it is #used in the procedure `IsBad1` below. IsBad2:=proc(w,fp1,B) local i: for i from 1 to nops(fp1) do if w[i]<>fp1[i] and fp1[i]<>B then return(false): fi: od: true: end: ### #IsBad1(w,fp1,B): returns true iff the word w contains the pattern fp1. IsBad1:=proc(w,fp1,B) local i: if fp1=[] then return(true): elif nops(fp1)>nops(w) then return(false): fi: for i from 1 to nops(w)-nops(fp1)+1 do if IsBad2(w[i..i+nops(fp1)-1],fp1,B) then return(true): fi: od: false: end: ### #IsBad(w,FP,B): returns true iff the word w contains at least one of #the members of the set of patterns FP. IsBad:=proc(w,FP,B) local fp1: for fp1 in FP do if IsBad1(w,fp1,B) then return(true): fi: od: false: end: ### #SetWnS(A,FP,B,n): contructs the set of n-letter words in the alphabet A #not containing any of the patterns of FP SetWnS:=proc(A,FP,B,n) local S,T,w: S:=AllWords(A,n): T:={}: for w in S do if not IsBad(w,FP,B) then T:=T union {w}: fi: od: T: end: ### #WnS(A,FP,B,n): #Inputs #(i) A: a set of symbols (the alphabet) #(ii) FP: a set of forbidden patterns, given as a list #(iii) B: a symbol for blank #(iv) n: a positive integer #Outputs: #the number of words in A of length n that AVOID all patterns in FP. WnS:=proc(A,FP,B,n): nops(SetWnS(A,FP,B,n)): end: ################################################################################ #3 #The first 15 terms of: #WnS({0,1},{[1,1,1],[1,B,1,B,1],[1,B,B,1,B,B,1],[1,B,B,B,1,B,B,B,1], #[1,B\$4,1,B\$4,1],[1,B\$5,1,B\$5,1]},B,n); #2, 4, 7, 13, 23, 40, 65, 106, 169, 278, 443, 705, 1117, 1760, 2807 #WnS({0,1}, { [1,1,1],[1,B,1,B,1],[1,B,B,1,B,B,1],[1,B,B,B,1,B,B,B,1], #[1,B\$4,1,B\$4,1],[1,B\$5,1,B\$5,1],[0,0,0],[0,B,0,B,0],[0,B,B,0,B,B,0], #[0,B,B,B,0,B,B,B,0], [0,B\$4,0,B\$4,0],[0,B\$5,0,B\$5,0]},B,n); #2, 4, 6, 10, 14, 20, 16, 6, 0, 0, 0, 0, 0, 0, 0 ################################################################################ #4 #SFP(d,n): SFP:=proc(d,n) local FP,i,j: FP:={}: if n