0
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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}

$\endgroup$
1
$\begingroup$

$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$.

$\endgroup$

Your Answer

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

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