Comment puis-je construire une grammaire qui génère ce langage?

Je suis étudiant pour un test de grammaires fini et automates & je suis coincé avec cette question:Comment puis-je construire une grammaire qui génère ce langage?

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

Je crois que mes productions devraient accompagner ces lignes:

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

Comment ma production pour C se souvenir des nombres de m et n? Je devine que ceci doit plutôt être une grammaire sans contexte, si oui, comment devrait-il être?

Source

2009-06-20 andandandand

Si cela avait été des devoirs que je l'aurais marqué ce, comme je l'ai dit, je suis étudiant pour une tester. Je prends le tag de devoirs. Man, Homework! = Test – andandandand

Pourquoi tant de défensive sur l'étiquette des devoirs? Étudier pour un test ressemble à des devoirs ou au moins «travail scolaire» et l'étiquette aide les personnes à la recherche de telles questions à trouver celui-ci. – CoderDennis

En fait, c'est la partie "automates et grammaires finies" qui ressemble à des devoirs. Peu importe si c'est pour un test ou non. – CoderDennis

On dirait que ce devrait être comme:

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

Vous devez forcer C'c à compter au cours du processus de construction. Afin de montrer qu'il est sans contexte, je considérerais utiliser Pump Lemma.

Source

2009-06-20 16:02:18

Je peux confondre une certaine définition, mais puisque les règles de production ont toutes un seul non-terminal sur le côté gauche, n'est-ce pas trivialement une grammaire sans contexte? – Svante

En fait, puisque m et n ont juste besoin d'être> = 0, votre grammaire est légèrement incorrecte. En voici un qui fonctionne: A-> aAc | B B-> bBc | (epsilon) – rofrankel

merci pour la correction –

Oui, cela ne sonne comme les devoirs, mais un soupçon:

Chaque fois que vous matcher un 'a', vous devez correspondre à un 'c'. Idem pour faire correspondre un 'b'.

Source

2009-06-20 15:58:05

Merci. Cet 'indice' est en fait la réponse. Et non, ce n'est pas les devoirs. – andandandand

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

où e == epsilon et X est inutile, mais ajouté pour plus de clarté

Source

2010-12-04 08:00:33

S> aSc | A A> Băc | λ

Cela signifie que chaque fois que vous obtenez un au moins vous avez 1 c ou si vous obtenez a et b, vous devez avoir 2 c. J'espère que cela a été utile

Source

2013-05-14 04:15:18 Mohamud

Eh bien les gars, voilà comment je vais le faire:

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

Source

2016-02-16 14:58:21 slow

Comment puis-je construire une grammaire qui génère ce langage?

Répondre

Questions connexes