What will be the context-free grammar of $B= A_1.A_2 $ when $A_1 = \{0^n1^n|n\geq 0\}$ $A_2 = \{1^n0^n|n \geq 0\}$ Also verify using a string.

if the Grammar for $A_1$: $S_1 \rightarrow 0S_11 | \varepsilon$

$A_2$: $S_2 \rightarrow 1S_20 | \varepsilon$

I am stuck with the value of $S \rightarrow$ ?

  • $\begingroup$ We are not here to do your homework. Please show that you have tried solving this by yourself, and ask precisions on the steps you are blocked. $\endgroup$
    – Nathaniel
    Apr 4, 2021 at 10:50
  • $\begingroup$ Nathaniel I am not asking you to do my homework, I did this using union I am stuck with concatenation, I have created separate grammars for A1 and A2 which are A1:S1 → 0S11 | ε and A2: S2 → 1S20 | ε I am stuck with the value of S → ? $\endgroup$ Apr 4, 2021 at 11:14
  • 2
    $\begingroup$ You should edit your post to show what you have done, not write it in the comments. $\endgroup$
    – Nathaniel
    Apr 4, 2021 at 11:15

1 Answer 1


Your grammars for $A_1$ and $A_2$ seem correct. Since you want to compute the concatenation of $A_1$ and $A_2$, you just need to express this fact with the start symbols of $A_1$ and $A_2$.

$S \rightarrow S_1S_2$ is a way to do it.

You can check by computing the derivation that creates the word $001110$.

  • $\begingroup$ Do i check it like this [S = 0 S1 1 = 0 0S1 11 = 0011]. [S=1 S2 0=10]. S→S1S2 = 0011.10 = 001110 $\endgroup$ Apr 4, 2021 at 11:40
  • $\begingroup$ No, the first steps should be $S \rightarrow S_1S_2 \rightarrow 0S_11S_2 \rightarrow$… $\endgroup$
    – Nathaniel
    Apr 4, 2021 at 13:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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