A *Dyck path* is a finite list of $ 1$ ‘s and $ -1$ ‘s whose partial sums are nonnegative and whose total sum is $ 0$ . For example, `[1, 1, -1, -1]`

is a Dyck path. Rather than use $ 1$ and $ -1$ , it is common to use "U" and "D" for $ 1$ and $ -1$ , respectively, so we might write `UUDD`

instead. (These might be more familiar as *Dyck words*.)

It is well-known that Dyck paths have a standard "grammar." The "Dyck grammar" for a path $ P$ is

$ $ P = \epsilon \quad | \quad U P D P.$ $

This grammar is very useful because it lets us quickly compute the generating function which enumerates the number of Dyck paths of given lengths.

I am interested not in *all* Dyck paths, but *restricted sets* of Dyck paths. For example, consider the Dyck paths which avoid "peaks" (the bigram `UD`

) at positive even heights; `UUUDDD`

is such a path, while `UUDD`

is not. If we could devise an unambiguous grammar for such paths, then we could write down an equation for the generating function which counts them. (There is such a grammar. It requires two production rules – one for the paths which avoid peaks at even heights, and one for paths which avoid peaks at odd heights.)

This idea leads to a natural question:

Given a (possibly infinite) set of positive integers $ A$ , does there exist a finite, unambiguous context-free grammar which generates precisely the Dyck paths whose peaks avoid $ A$ ?

The answer (I think) is "yes" when $ A$ is finite or an arithmetic progression. I suspect that the answer is "no" in every other case, but I have no idea how to begin proving this.

For example, here is a special case that I cannot decide:

Is the set of Dyck paths which avoid peaks at positive squares a context-free language?