Short answer Among deterministic context–free languages (DCFLs), those that occur as the word problem of a finitely generated group are exactly the word problems of virtually free groups. This is a very small subclass of DCFLs, constrained by strong algebraic invariances (conjugation, inversion, free reduction). There is no known purely “language–theoretic” intrinsic characterization beyond these structural invariances; the sharpest description comes from group theory (Bass–Serre theory) or from viewing them as Dyck-like languages with a finite-state “decoration”.

More details

• Classification by groups: By the Müller–Schupp theorem, a finitely generated group has context–free word problem iff it is virtually free. Moreover, for such groups the word problem is not just context–free but deterministic context–free. Thus the “group side” is completely classified: the groups are precisely the finite-index extensions of free groups (equivalently, fundamental groups of finite graphs of finite groups).

• Invariance and normal-subgroup viewpoint: Fix a finite symmetric generating set Σ (closed under inverse). For any group G, its word problem WP(G) ⊆ Σ* has the following language-theoretic properties, which already exclude most DCFLs:

  • Closed under inversion/reversal: w ∈ WP(G) iff w^{-1} ∈ WP(G), where w^{-1} is obtained by reversing w and inverting letters.
  • Closed under conjugation: for all u, if w ∈ WP(G), then u w u^{-1} ∈ WP(G).
  • Free-reduction invariance: inserting or deleting xx^{-1} and x^{-1}x does not change membership. Equivalently, WP(G) = red^{-1}(N), the inverse image under free reduction of a normal subgroup N of the free group F(Σ); F(Σ)/N ≅ G. For virtually free G this N is such that the quotient is virtually free.

  Many familiar DCFLs do not satisfy these invariances (e.g. {a^n b^n}, deterministic but not closed under conjugation), so they can never be a group’s word problem.

• Dyck-structured description: From a language point of view, word problems of virtually free groups are “Dyck languages with a finite-state decoration.” Concretely, by Bass–Serre theory a virtually free group is a finite graph of finite groups; words equal to the identity correspond to well-nested traversals in the associated tree (a Dyck structure) interspersed with labels from the finite vertex groups (a regular constraint). This yields:

  • WP(G) is accepted by a deterministic pushdown automaton (indeed in real time; no ε-moves are needed).
  • You can view WP(G) as obtained from a Dyck language of some rank by inserting regular languages in a finite-state-controlled way, respecting the involution (this mirrors passing from a free group to its finite-index extensions).

  This explains both determinism and the strong invariances above.

• Growth and further restrictions: If G is infinite and virtually free, WP(G) has exponential growth in word length (e.g. for free groups the number of trivial words of length 2n grows like a Catalan-type sequence times an exponential factor). Hence DCFLs with subexponential growth (like {a^n b^n}) cannot be group word problems unless the group is finite (in which case WP is regular).

• Fine structure inside the class:

  • Finite groups ⇔ regular word problems (Anisimov’s theorem).
  • Virtually cyclic (finite-by-Z) groups ⇔ deterministic one-counter word problems.
  • Non-virtually-cyclic virtually free groups ⇔ genuinely pushdown (not one-counter). All are deterministic.

• Dependence on generating set: Whether the word problem is context–free (hence deterministic) is independent of the finite generating set, since changes of generators induce rational transductions that preserve context-freeness. But the exact language WP(G) depends on the chosen symmetric generating set.

What we do not have There is (so far) no purely language-theoretic intrinsic characterization of the subclass of DCFLs that are group word problems which avoids reference to groups (or to normal subgroups of free groups) beyond the obvious invariances above. The best practical descriptions are:

• “WP(G) is the inverse image under free reduction of a normal subgroup N ≤ F(Σ) with F(Σ)/N virtually free,” or
• “A deterministic pushdown language with a Dyck/nesting core and only regular ‘local’ constraints,” as forced by the graph-of-groups normal forms.

References

• D. E. Muller and P. E. Schupp, Groups, the theory of ends, and context-free languages, J. Comput. Syst. Sci. 26 (1983), 295–310.
• For background on the Dyck-like structure via Bass–Serre theory and on DPDA recognizability of virtually free word problems, see also: Epstein et al., Word Processing in Groups (1992), and expository papers by Gilman on formal languages and groups.

Summary Inside DCFL, the word problems of finitely generated groups form a very rigid subclass: exactly those coming from virtually free groups, hence deterministic, real-time, conjugacy- and inversion-invariant, with a Dyck-like nested structure. This rules out the vast majority of DCFLs, and apart from these structural invariances and the group-theoretic description, no broader internal characterization is known.