A doubt with question:

What is the grammar that generates the language quoted in the description? $$a^nb^{n+m}c^m\text{ for }n≥0, m≥0$$

I don't understand this.

  • 1
    $\begingroup$ Do you know what a grammar is, and what a language is ? $\endgroup$ – Denis Sep 10 '13 at 23:58

The goal is to find a grammar with rules that generate all the words of the form you describe, one example of theses words is $aabbbbbccc$ for $n=2$ and $m=5$.

The following grammar works, with initial symbol $S$ and variables $A,B$:

$\begin{array}{l} S\to AB\\ A\to aAb\\ A\to\epsilon\\ B\to bBc\\ B\to\epsilon \end{array}$

Where $\epsilon$ is the empty word.

For instance to obtain the word above, you can do $S\to AB\to aAbB\to aaAbbB\to aabbB\to aabbbCc\to aabbbbCcc \to aabbbbbCccc \to aabbbbbccc$.


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.