-3
$\begingroup$

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! :)

$\endgroup$
  • $\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 '19 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 '19 at 15:58
  • $\begingroup$ I need to find the production rule of this grammar $\endgroup$ – Huy Vũ Apr 4 '19 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 '19 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 '19 at 16:07
1
$\begingroup$

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?

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Yes. I see it. Thanks a lot $\endgroup$ – Huy Vũ Apr 4 '19 at 16:55
  • $\begingroup$ Welcome to the site! $\endgroup$ – John L. Apr 4 '19 at 17:02

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