Comment puis-je construire une grammaire qui génère ce langage?
-
06-07-2019 - |
Question
J'étudie pour un automate fini & amp; grammaires test et je suis coincé avec cette question:
Construct a grammar that generates L:
L = {a^n b^m c^m+n|n>=0, m>=0}
Je pense que mes productions devraient aller dans ce sens:
S->aA | aB
B->bB | bC
C->cC | c Here's where I have doubts
Comment ma production pour C peut-elle mémoriser le nombre de m et de n? Je suppose que cela doit plutôt être une grammaire sans contexte, si oui, comment devrait-elle être?
La solution
On dirait que cela devrait être comme:
A->aAc | aBc | ac | epsilon
B->bBc | bc | epsilon
Vous devez obliger C'c à compter pendant le processus de construction. Afin de montrer qu'il est sans contexte, je considérerais d'utiliser Lemme de pompe .
Autres conseils
Oui, cela ressemble à un devoir mais un indice:
Chaque fois que vous faites correspondre un "a", vous devez faire correspondre un "c". Pareil pour faire correspondre un 'b'.
S -> X
X -> aXc | Y
Y -> bYc | e
où e == epsilon
et X
sont inutiles mais
ajouté pour plus de clarté
S- > aSc | A A- > bAc | & # 955;
Cela signifie que chaque fois que vous obtenez a, vous avez au moins 1 c ou si vous obtenez a et b, vous devez en avoir 2 c. J'espère que cela a été utile
Eh bien les gars, voici comment je vais le faire:
P={S::=X|epsilon,
X::=aXc|M|epsilon,
M::=bMc|epsilon}