7
$\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}$?

$\endgroup$
11

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.