Contexte libre grammaire pour unaire Addition

Question

Étant donné un alphabet de 1s je veux analyser plus de la forme

1^k + 1^j = 1^k+j 

Ceci est assez facile de représenter avec un automate pushdown simplement en appuyant sur un 1 sur la pile sur chaque des deux premiers 1, puis sauter sur le dernier ensemble de 1s. Cependant, je n'arrive pas à comprendre comment représenter ceci comme une grammaire sans contexte, ce qui est évidemment possible depuis PDA == CFG.

Answer 1

Mon conseil est de faire un point de départ simple: 1 + 1 = 11 Et maintenant essayez de comprendre comment vous pouvez "croître" avec des expressions CFG légales. Sinon, j'ai résolu cela tout à l'heure en essayant de l'étendre avec "parenthèse correspondante", qui est un problème d'introduction commun aux CFG. C'est évidemment plus difficile, mais vous pouvez trouver un chemin fructueux de cette façon.

Espérons que cela aide! Bonne chasse.

Agor

Answer 2

Si vous réécrivez l'ERS comme 1^j1^k, alors vous devriez le voir est juste deux ensembles imbriqués de 1 balancées. Combiné avec un "cas de base" de 1 + 1 = 11, vous devriez être capable de faire pousser les "j" à l'intérieur et les "k" à l'extérieur.

Answer 3

Oui, celui-ci me dérange depuis une heure.

En outre, cdiggins, 1 + 1 = 111 passerait que

Answer 4

je suis Workin sur ce n'a jamais été aussi et ne peux pas le faire fonctionner. c'est ce qui fait le plus de sens pour moi:

A -> B + B = BB B -> BB B -> 1

mais oui, cela accepte des chaînes comme 1 + 111 = 11 et 11 + 1 = 111111 et d'autres non-sens. On dirait que les gens ici savent mais n'ont pas envie de partager. Ce n'est pas exactement quelque chose que nous pouvons google et obtenir une aide significative. pense que tu pourrais être un peu plus utile?

Answer 5

Ajout unaire générique impossible avec une grammaire sans contexte ou avec un automate à pile. Pour ce type de calcul, vous devez utiliser une machine de Turing. Ecrire un automate à pile qui pousse les 1 sur la pile n'est pas valide car la pile n'est pas vraiment la sortie d'un PDA. La seule sortie d'un PDA est un binaire "Accept" ou "Reject" qui indique si la chaîne d'entrée fait ou non partie du langage reconnu par le PDA.

Answer 6

S -> 1 + 1 = 11 
S -> 1S1 
S -> 1 + 1A11 
A -> 1 = 1 
A -> 1A1 

Answer 7

S => 1A1 
A => 1A1 | +1B1 
B => 1B1 | = 

Les deux premières rangées construisent le premier terme de la somme et ayant le même nombre d'unités. Une fois le premier terme construit, vous passez à la seconde avec "A => + 1B1". La troisième ligne construit le second terme, en ajoutant simultanément un nombre égal d'unités à la somme. Une fois que vous avez terminé, la transition d'égalité le termine.

Notez que cela n'autorise aucun terme dans l'expression à être égal à zéro.Aussi, vous pouvez construire des expressions unaires moins avec une légère variation, en gardant à l'esprit que a - b = c est équivalent à a = b + c

Answer 8

Je sais que c'est une vieille question, je lisais Godel, Escher, Bach et a été frappé sur le même problème (de générer un Grammer pour son système pq)

donc, pour la question de l'OP, je suppose que les règles de production suivantes devrait faire:

premier -> 1 + seconde1 | 1first1 second -> 1 = 1 | 1second1