Créer un CFG pour les langues suivantes

Question

Je me demandais juste si mon CFG est correct pour la première langue.

Les langues suivantes sont sur l'alphabet {a, b, c}

première langue

{XCY | x et y sont des chaînes avec le même nombre de} de

Mon CFG

S -> AaASAaA | c | AcA

A -> AA | b | c | epsilon

langue seconde

{a^ib^jc^k | i> = j + k}

Dans ma classe, nous avons prouvé que le même langage n'a pas de CFG si i = j = k, comment est-ce différent? Est-ce que cela a même un CFG? Si c'est le cas, je ne peux pas penser à une sorte de cfg qui produit ce langage, le seul que je peux penser satisfait simplement que le nombre de a est supérieur ou égal au nombre de b plus le nombre de c, où l'ordre n'a pas d'importance.

Answer 1

Votre CFG pour la première langue est correcte, même si je préférerais écrire un sans ambiguïté comme ceci:

A -> epsilon | Ab | Ac 

langue seconde:

S -> M | aS 
M -> N | aMc 
N -> epsilon | aNb 

Note: oui, cela est un problème de travail , mais je ne pense pas que fournir ici une réponse ruine cette expérience d'apprentissage particulière. Une fois que vous le voyez, vous l'obtenez, et si vous ne l'obtenez pas, vous pouvez vous heurter la tête pendant longtemps sans rien obtenir.