1
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – vonbrand
    May 26 at 15:55
  • 3
    $\begingroup$ @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.) $\endgroup$ May 26 at 17:03
  • 1
    $\begingroup$ Please do not post the same question on multiple sites. $\endgroup$
    – D.W.
    May 26 at 22:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.