In this paper the problem of optimal input design for model identification is studied. The optimal input signal is designed by maximizing a scalar cost function of the information matrix, where the input signal is a realization of a stationary process with finite memory, with its range being a finite set of values. It is shown that the feasible set for this problem can be associated with the prime cycles in the graph of possible values and transitions for the input signal. A realization of the optimal input signal is generated by running a Markov chain associated with the feasible set, where the transition matrix is built using a novel algorithm developed for de Bruijn graphs. The proposed method can be used to design inputs for nonlinear output-error systems, which are not covered in previous results. In particular, since the input is restricted to a finite alphabet, it can naturally handle amplitude constraints. Finally, our approach relies on convex optimization even for systems having a nonlinear structure. A numerical example shows that the algorithm can be successfully used to perform input design for nonlinear output-error models. (C) 2014 Elsevier Ltd. All rights reserved.