Repetition-Free Derivability from a Regular Grammar is NP-Hard
  We prove the NP-hardness of the problem whether a given word can be derived from a given regular grammar without repeated occurrence of any nonterminal. 
Jochen Burghardt
cs.FL cs.CC