One of the efficient design methodologies for large scale system on a chip (SoC) is IP-based design. In this methodology, a system is considered as a set of components and interconnects among them. The designers try to reuse existing IPs as much as possible. Communications among components have to be conducted using a common protocol, however, IPs available today use various communication protocols. Thus the protocol conversion is one of the most important topics in IP-based design (Gajski et al., 2000). In this paper, we propose a method for automatic protocol transducer synthesis which is applicable to complex protocols. The main idea of our proposed method is division of the exploration space into smaller ones for avoiding explosion of the exploration space, namely with a divide and conquer approach. We demonstrate our method by synthesizing transducers which translate between the real and complicated protocols with advanced features such as non-blocking transactions and out-of-order transactions.