context free grammar design

Question

Design a context free grammar and PDA for the following language.

$$\Sigma = \{0,1\},\qquad L = \left\{uv \mid u \in \sum^{*} \;v\in \sum^{*}1\sum^{*} \text{ with }|u| \geq |v| \right\}$$

I'm not sure how to approach this problem, especially the CFG part. Can anyone tell me how to solve it?

Answer 1

I will give my intuition of the problem. A formal proof is not much harder to produce.

Since we want $|u| \ge |v|$, we can always push the first $\Sigma^*$ part of $v$ into $u$. This does not alter $uv$, but it increases $|u|$ and decreases $|v|$, making $|u| - |v|$ greater. This simplifies the language a little bit:

$$ L = \left\{uv \mid u \in \Sigma^*, v \in 1\Sigma^*, |u| \ge |v|\right\} $$

So, you can start with $01$ or $11$, which are the only two shortest strings of $L$. Then you build it up by adding things to the front and to the back, but you retain the inequality $|u| \ge |v|$ by not adding anything to the back ($v$) if nothing is added to the front ($u$). This gives the following CFG:

\begin{align} L & \to 01 \\ L & \to 11 \\ L & \to 0L \\ L & \to 1L \\ L & \to 0L0 \\ L & \to 0L1 \\ L & \to 1L0 \\ L & \to 1L1 \\ \end{align}

Answer 2

$L$ is the set of words over $\{0,1\}$ of the form $uv$, where $|u|\ge|v|$, and $v$ contains at least one $1$. The condition that $|u|\ge |v|$ suggests a production of the form $$X\to 0X0\mid 0X1\mid 1X0\mid 1X1\mid 0X\mid 1X\;$$ that generates a symbol on the left whenever it generates one on the right; the problem is to ensure that we get at least one $1$ on the right. Here’s one approach; $S$ is the initial symbol, and $\lambda$ is the empty word.

$$\begin{align*} &S\to X\\ &X\to 0X0\mid 0X1\mid 1X0\mid 1X1\mid 0X\mid 1X\mid Y\\ &Y\to 0Z1\mid 1Z1\\ &Z\to 0Z0\mid 0Z1\mid 1Z0\mid 1Z1\mid 0Z\mid 1Z\mid\lambda \end{align*}$$

The $X$ productions generate any string of the form $uYv$ such that $|u|\ge|v|$; the $X$ and $Y$ productions together generate any string of the form $uZ1v$ such that $|u|\ge|1v|$; and the $X$, $Y$, and $Z$ productions generate $L$. If you play with the grammar a bit, you can eliminate the $\lambda$ production, if you want. This is an especially straightforward way to design the grammar, but there are others that produce shorter grammars. You might try, for instance, to eliminate $Y$ and use only $X$ and $Z$.