# Context Sensitive Grammar for the language $\{a^n b^n c^{2+k}\mid n \ge 1, 0 \le k\le 1\}$ [closed]

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

• 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. – dkaeae Apr 4 '19 at 15:57
• 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? – David Richerby Apr 4 '19 at 15:58
• I need to find the production rule of this grammar – Huy Vũ Apr 4 '19 at 16:00
• Yes, we know what the exercise is. What do you need help with? Be more specific than "I need help solving the exercise." – David Richerby Apr 4 '19 at 16:02
• 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 – Huy Vũ Apr 4 '19 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?

• Yes. I see it. Thanks a lot – Huy Vũ Apr 4 '19 at 16:55
• Welcome to the site! – John L. Apr 4 '19 at 17:02