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?