0
$\begingroup$

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

$\endgroup$
3
  • $\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 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$ – Aqsa Nadeem Apr 4 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 at 11:15
2
$\begingroup$

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

$\endgroup$
2
  • $\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$ – Aqsa Nadeem Apr 4 at 11:40
  • $\begingroup$ No, the first steps should be $S \rightarrow S_1S_2 \rightarrow 0S_11S_2 \rightarrow$… $\endgroup$ – Nathaniel Apr 4 at 13:31

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.