Considering applications in plan recognition, we study how shuffle operators can be incorporated into language models that also capture the context-free languages. Our aim is to provide a formal framework for plan recognition, in which the balance between expressive power and computational tractability can be tuned through natural restrictions on the model. We also study the complexity of the membership problem for various restrictions of the suggested model.