ISI2015-PCB-CS-5b

Question

Construct a context free grammar (CFG) to generate the following language:

$L = \{a^nb^mc^{n+m}: \text{n, m are integers, and } n \geq 1, m \geq 1 \}$

Comments

Since we have #c = #a + #b, so whenever we generate one a or one b, make sure one c is also generated along with it.

Answer 1

 Given Context free language is :

$L=\{ a^nb^mc^{n+m} : \text{ n,m are integers,} n \geq 1 m \geq 1\}$ .

For clarity given language can be interpreted  as

$L=\{ a^nb^mc^mc^n : \text{n,m are integers,} n \geq 1 m \geq 1\}$.

Now the given language is clearly DCFL .

And context free grammar (CFG) of the following language:

$S \to aSc \mid aAc$

$A \to bAc \mid bc$

Comments

this grammar doesn't generate string "ccab", so maybe the given grammar needs some more transformations?

---

@toxicdesire why do you want to generate the string "ccab" ?

---

@toxicdesire "ccab" is not a string of the given language, as all strings must start with "a". So ccab need not be generated by the given grammar.