Come posso costruire una grammatica che generi questa lingua?
-
06-07-2019 - |
Domanda
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?
Soluzione
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 .
Altri suggerimenti
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".
S -> X
X -> aXc | Y
Y -> bYc | e
dove e == epsilon
e X
non sono necessari ma
aggiunto per chiarezza
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
Bene ragazzi, ecco come lo farò:
P={S::=X|epsilon,
X::=aXc|M|epsilon,
M::=bMc|epsilon}