Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
Do you know what a grammar is, and what a language is ? –  Denis Sep 10 '13 at 23:58
add comment

1 Answer

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$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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