Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am looking for a context-sensitive grammar $G$ for the language $$L = \left\{w \in \left\{0,1\right\}^* | \; |w|_0 \geq |w|_1 \right\}$$ where $|w|_0$ means the amount of the terminal $0$ in the word $w$.

I know how to create a PDA for this by "remembering" the amout of $1$'s, but I do not know how to create a Grammar (respectively the production rules).

Could you please help me finding the answer? Is there a general way of "converting" a PDA definition to grammar rules?

Thanks in advance!

share|cite|improve this question
up vote 1 down vote accepted

Since you can recognize the language with a PDA, it must be context-free, so we can do better than a context-sensitive grammar. Here’s a context-free grammar that should work; $S$ is the initial symbol, $\lambda$ is the empty string, $E$ is intended to generate words with an equal number of $0$’s and $1$’s, and $U$ is intended to generate words with more $0$’s than $1$’s.

$$\begin{align*} &S\to U\\ &U\to E0U\mid E0E\\ &E\to 0E1E\mid 1E0E\mid\lambda \end{align*}$$

(I don’t really need $U$: I could use $S$ instead.)

The basic idea is that there has to be at least one extra $0$; the second production generates it, possibly preceded by a string with an equal number of $0$’s and $1$’s; what follows it may but need not have excess $0$'s.

There is an algorithm for converting a non-deterministic PDA to a CFG, but it’s fairly complicated. (The opposite direction is easier.) One version is outlined in these notes starting at page 9. These notes do it a little differently and in pretty full detail.

share|cite|improve this answer
Thank you, great! – muffel Oct 10 '11 at 14:28

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.