1
$\begingroup$

Here is an exercise from an introduction to computation class:

Show that the following context-free grammar $G$ generates the language $L$ of words over $\{0,1\}$ with an equal number of $0$s and $1$s: $$ S \to \epsilon \mid SS \mid 0S1 \mid 1S0 $$

How should I prove that $L⊆ L(G)$ and $L(G) ⊆ L$?

I think I should start with the difference of 0's and 1's but have no clue where to start.

$\endgroup$
1
2
$\begingroup$

One direction is easy. To prove that $L(G) \subseteq L$, we prove by induction on the length of the derivation that every word generated by $G$ has an equal number of 0s and 1s. This amounts to proving the following statements:

  • $\epsilon \in L$.
  • If $x,y \in L$ then $xy \in L$.
  • If $x \in L$ then $0x1,1x0 \in L$.

The other direction, proving that $L \subseteq L(G)$, is more challenging. We have to show that every word in $L$ is generated by $L(G)$. The proof is by induction on the length of the word. The base case, which is the empty word, is easy. Now consider any non-empty words $w = \sigma_1 \ldots \sigma_n \in L$. Let $\delta(i) = \#_1(\sigma_1 \ldots \sigma_i) - \#_0(\sigma_1 \ldots \sigma_i)$. The sequence $$ \delta(0), \ldots, \delta(n) $$ starts and ends with $0$, and each element differs from the preceding one by $\pm 1$. Suppose that $\delta(1) = 1$, hence $\sigma_1 = 1$. Let $i$ be the minimal index $i > 0$ such that $\delta(i) = 0$ (such an index exists since $\delta(n) = 0$). Then $\delta(i-1) = 1$, hence $\sigma_i = 0$. You can check that $x = w_2 \ldots w_{i-1}$ and $y = w_{i+1} \ldots w_n$ are both in $L$. By induction, $S \Rightarrow^* x,y$. Therefore $$S \Rightarrow SS \Rightarrow 1S0S \Rightarrow^* 0x1y = w.$$ If $\delta(1) = -1$ then instead we use the rule $S \Rightarrow 0S1$.

$\endgroup$
2
  • $\begingroup$ Hey, thanks for answering the question. I think I have some idea about how to elaborate L⊆L(G) but I am still not 100% sure where to start. I already finished the base case which is the empty string, how should I write the induction hypothesis? I am thinking about suppose |w| is in L(G) and prove for |w+2| is in L(G) as well but I am kinda stucked here. $\endgroup$ Mar 17 at 17:30
  • $\begingroup$ The proof is by complete induction on the length of the word. I outlined the argument in my answer. $\endgroup$ Mar 17 at 18:08

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.