We consider the problem of generating strings that belong to certain languages and satisfy some additional restrictions. Languages are defined by formal grammars and automata. The following formulation of this problemas a decision one is proposed: for a language represented by a formal grammar or an automaton and a pair of strings, determine whether there exists a string in this language that lies lexicographicallybetween these strings. It is proved that this problemis NLOGSPACE-complete for deterministic and nondeterministic finite automata and for linear context-free grammars; P-complete for context-free grammars of the general form; NP-complete for alternating finite automata, for conjunctive grammars and for linear conjunctive grammars; PSPACE-complete for context sensitive grammars and linear bounded automata.