grammaire hors-contexte et inversion

Question

Je suis la conception d'une grammaire hors-contexte pour générer cette langue:

{ w in {a,b}* | w is of the form uvu^R, where u and v are any strings in {a,b}* } 

Je définirais les deux premières chaînes comme:

U -> aU | bU | _ 
V -> aV | bV | _ 

Et puis combiner les :

S -> UV 

Mais comment exprimer l'inversion comme une grammaire sans contexte?

Answer 1

Vous devez utiliser le contexte sans-ness de la grammaire (ce que vous présentez est à ce jour juste une grammaire régulière):

U-> aUa | bUb | a | b | _ 

correspondra à des choses comme « abeba » et " aabaa ", mais pas" aabba ".

Je vous laisse le soin de modifier cela selon vos besoins - mais gardez à l'esprit que la langue spécifiée a la possibilité de u étant la chaîne vide, donc elle génère toutes les chaînes dans {a,b}*.