# Unambiguous formal grammars for a specific class of languages

Suppose that $$w \in \{0; 1\}^*$$ is a binary word. Let's denote the number of $$0$$-s in $$w$$ as $$\#_0(w)$$ and the number of $$1$$-s in $$w$$ as $$\#_1(w)$$.

Now suppose that $$q \in \mathbb{Q}$$ is a positive rational number. Consider the language $$L_q \subset \{0; 1\}^*$$ of all words $$w$$, such that for any its prefix $$p$$ we have $$\#_0(p) \leq q \#_1(p)$$. For example, $$L_1$$ is the language of all possible prefixes of Dyck words.

It is not hard to see, that $$L_q$$ is deterministic context-free for any $$q$$. Indeed, if $$q = \frac{m}{n}$$ for some natural $$m$$ and $$n$$ we can build a following deterministic pushdown automaton that recognises our language. It has the following states:

State $$0$$: Reads an element from the input. If it is $$1$$, adds $$m$$ elements to the stack and remains in the State $$0$$. If it is $$0$$, moves to State $$1$$. This is both the initial state and the only final state.

State $$i$$ (for $$1 \leq i \leq n-1$$): Does not read input, but tries to read from the stack. If it succeeds, the stack has $$1$$ element less, and we transit to State $$i+1$$. If it fails because the stack was empty, we transit to State $$-1$$.

State $$n$$: Does not read input, but tries to read from the stack. If it succeeds, the stack has $$1$$ element less, and we transit to State $$0$$. If it fails because the stack was empty, we transit to State $$-1$$.

State $$-1$$: Reads input but does nothing. Nothing ever leaves this state.

Note, that this automaton is a final-state one. It stops when it attempts to read the input and finds that it has ended. It accepts the input if it stops in a final state.

From the fact, that $$L_q$$ is deterministic context-free we can conclude, that it is unambiguous. My question is:

How can we explicitly build unambiguous formal grammars for $$L_q$$ for arbitrary $$q \in \mathbb{Q}$$?

This question on MSE

• The PDA model doesn't allow any kind of move if the stack is empty, even less "check if the stack is empty, if so...". You need to express this in some other way. May 26, 2021 at 15:55
• @vonbrand When the stack is used as a counter then we can safely use this terminology. The understanding is that there is a bottom-of-stack symbol that stays at the bottom and signifies "empty". (But I agree, not really empty.) May 26, 2021 at 17:03
• – D.W.
May 26, 2021 at 22:41