Wie kann ich eine Grammatik konstruieren, die diese Sprache erzeugt?

Question

Ich bin für einen endlichen Automaten & Grammatiken Test zu studieren, und ich bin mit dieser Frage fest:

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

Ich glaube, meine Produktionen entlang dieser Linien gehen sollte:

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

Wie kann meine Produktion für C erinnern die Zahlen m und n? Ich vermute, dies ist vielmehr eine kontextfreie Grammatik, wenn ja, wie es sein sollte?

Answer 1

Scheint, wie es sein sollte:

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

Sie müssen C'c zwingen, während Bauprozess gezählt werden. Um kontextfrei ist es zu zeigen, würde ich Pump Lemma zu verwenden, in Betracht ziehen.

Answer 2

Ja, das tut wie Hausaufgaben klingen, aber ein Hinweis:

Jedes Mal, wenn Sie ein ‚a‘ entsprechen, müssen Sie ein ‚c‘ entsprechen. Das Gleiche gilt für Anpassen einer 'b'.

Answer 3

S -> X
X -> aXc | Y
Y -> bYc | e

wo e == epsilon und X ist nicht notwendig, aber hinzugefügt, um Klarheit

Answer 4

S-> aSc | A A-> bAc | λ

Das bedeutet, wann immer Sie eine zumindest erhalten Sie 1 c haben oder wenn Sie a und b erhalten müssen Sie 2 c haben. Ich hoffe, es hilfreich gewesen

Answer 5

Nun Jungs, das ist, wie ich es tun:

P={S::=X|epsilon,
   X::=aXc|M|epsilon,
   M::=bMc|epsilon}