I'm studying for my final exam and come up with this exercise with no idea how to find the production rule of this grammar.

I need help. Thanks all of you! :)


closed as unclear what you're asking by David Richerby, Evil, Discrete lizard Apr 5 at 8:49

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ Welcome to Computer Science! What did you try? Where did you get stuck? Would you please add any of your attempts towards a solution to the question text? Thank you. $\endgroup$ – dkaeae Apr 4 at 15:57
  • 2
    $\begingroup$ Isn't this just a simple variant of the grammar for $\{a^nb^n\mid n\geq 1\}$? can you be more specific about what you need help with? $\endgroup$ – David Richerby Apr 4 at 15:58
  • $\begingroup$ I need to find the production rule of this grammar $\endgroup$ – Huy Vũ Apr 4 at 16:00
  • 1
    $\begingroup$ Yes, we know what the exercise is. What do you need help with? Be more specific than "I need help solving the exercise." $\endgroup$ – David Richerby Apr 4 at 16:02
  • $\begingroup$ I need help to find the production rule of the language. Something like S -> aAb. Sorry for my English because i've not been taught this subject in English $\endgroup$ – Huy Vũ Apr 4 at 16:07

Here is the hint.

The grammar of a union is the union of the grammars.

That is, the grammar for $L_1$ and $L_2$ is the "union" of $G_1$ and $G_2$, where $G_1, G_2$ is the grammar for $L_1$ and $L_2$ respectively. Instead of a formal definition, let me use an example to illustrate the meaning of the strategy.

Suppose the grammar for language $L_1$ is:
$\quad S\to aSbS \mid ST \mid \epsilon$
$\quad T\to Tab \mid \epsilon$
Suppose the grammar for language $L_2$ is:
$\quad S\to bSaS \mid T $
$\quad T\to aT \mid \epsilon$
Then the grammar for $L_1\cup L_2$ is:
$\quad S\to S_1 \mid S_2$
$\quad S_1\to aS_1bS_1 \mid S_1T_1 \mid \epsilon$
$\quad T_1\to T_1ab \mid \epsilon$
$\quad S_2\to bS_2aS_2 \mid T_2 $
$\quad T_2\to T_2a \mid \epsilon$
where all nonterminals for $L_1$ are added subscript ${}_1$ and all nonterminals for $L_2$ are added subscript ${}_2$ and, finally, a new rule $S\to S_1\mid S_2$ is added.

Can you see how to decompose the language given in the title into smaller pieces so as to apply this strategy?

  • $\begingroup$ Yes. I see it. Thanks a lot $\endgroup$ – Huy Vũ Apr 4 at 16:55
  • $\begingroup$ Welcome to the site! $\endgroup$ – Apass.Jack Apr 4 at 17:02

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