Abstract: In robot program synthesis, instruction sequence can be searched as program. The program synthesis method based on Markov transfer matrix has the advantages of easy to access and strong generalization ability. However, due to the search efficiency, only simple sequences can be synthesized, which limits the ability of program synthesis. This paper proposes three optimization methods, including redundant optimization, greedy optimization and state compression search, to reduce the search space and improve the ability of the program synthesis. Redundancy optimization optimized candidate programs by checking their subsequences and removing redundant instructions. Greedy optimization analyzed the movement instructions in the program, gave priority to the search instructions moving to the target location to optimizes the search direction. State compression merged the same search state and solved the problem of local repeated search. Experimental results based on these three methods prove that these three methods can reduce the search times and improve the ability of program synthesis.