fa={{1,1}{1,0},{1,0}{2,1},{2,1}{2,1},{2,0}{1,0}};
FAApply[rule_,s0_,list_]:=FoldList[{First[#1],#2}/.rule&,{s0},list]
FAStep[rule_,s0_,list_]:=Map[Last,Rest[FoldList[{First[#1],#2}/.rule&,{s0},list]]]
FAEvolveList[rule_,s0_,init_,t_]:=NestList[FAStep[rule,s0,#]&,init,t]
RasterGraphics[data_]:=Graphics[Raster[1-Reverse[data]],AspectRatioAutomatic]
RasterGraphics[data_,lab_]:=Graphics[Raster[1-Reverse[data]],AspectRatioAutomatic,PlotLabellab]
Show[RasterGraphics[FAEvolveList[fa,1,Table[0,{100}],60]]];
ToFARule[n_Integer,{s_Integer,k_Integer}]:=Flatten[MapIndexed[{1,-1}#2+{0,k}Mod[Quotient[#1,{k,1}],{s,k}]+{1,0}&,Partition[IntegerDigits[n,sk,sk],k],{2}]]
RasterGraphics[data_,lab_]:=Graphics[Raster[1-Reverse[data]],AspectRatioAutomatic,PlotLabellab]
Show[GraphicsArray[Partition[Table[RasterGraphics[FAEvolveList[ToFARule[i,{2,2}],1,Table[0,{40}],30],i],{i,0,255}],8]]];
FAMap[rule_,s0_,n_,k_:2]:=Table[{i,FromDigits[FAStep[rule,s0,IntegerDigits[i,k,n]],k]},{i,0,k^n-1}]
FAMapMatrix[rule_,s0_,n_,k_:2]:=Normal[SparseArray[((#+1)1)&/@FAMap[rule,s0,n],{k^n,k^n}]]
Show[RasterGraphics[FAMapMatrix[fa,1,8]]];
Use a simple heuristic to find "interesting" cases: