views:

552

answers:

2

I'm studying for a finite automata & grammars test and I'm stuck with this question:

Construct a grammar that generates L:
L = {a^n b^m c^m+n|n>=0, m>=0}

I believe my productions should go along this lines:

    S->aA | aB
    B->bB | bC
    C->cC | c Here's where I have doubts

How can my production for C remember the numbers of m and n? I'm guessing this must rather be a context-free grammar, if so, how should it be?

+2  A: 

Yes, this does sound like homework, but a hint:

Every time you match an 'a', you must match a 'c'. Same for matching a 'b'.

Scott
Thanks. That 'hint' is actually the answer. And no, it's not homework.
omgzor
+5  A: 

Seems like it should be like:

A->aAc | aBc | ac | epsilon
B->bBc | bc | epsilon

You need to force C'c to be counted during construction process. In order to show it's context-free, I would consider to use Pump Lemma.

Artem Barger
I may be confusing some definition, but since the production rules all have only a single nonterminal on the left side, isn't this trivially a context-free grammar?
Svante
Actually, since m and n just need to be >= 0, your grammar is slightly incorrect. Here's one that works:A->aAc | BB->bBc | (epsilon)
endtime
thanks for correction
Artem Barger