Come posso costruire una grammatica che generi questa lingua?

Question

Sto studiando per automi e ampli finiti; test di grammatica e sono bloccato con questa domanda:

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

Credo che le mie produzioni dovrebbero seguire questa linea:

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

Come può la mia produzione per C ricordare i numeri di m e n? Immagino che debba piuttosto essere una grammatica senza contesto, in tal caso, come dovrebbe essere?

Answer 1

Sembra che dovrebbe essere come:

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

Devi forzare il conteggio di C'c durante il processo di costruzione. Per dimostrare che è privo di contesto, prenderei in considerazione l'uso di Pump Lemma .

Answer 2

Sì, questo suona come un compito, ma un suggerimento:

Ogni volta che abbini una 'a', devi abbinare una 'c'. Lo stesso vale per la corrispondenza di una "b".

Answer 3

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

dove e == epsilon e X non sono necessari ma aggiunto per chiarezza

Answer 4

S > aSc | A A- > BAC | & # 955;

Questo significa che ogni volta che ottieni almeno hai 1 c o se ottieni aeb devi avere 2 c. spero sia stato utile

Answer 5

Bene ragazzi, ecco come lo farò:

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