Comment obtenir la grammaire sans contexte et son PDA correspondant?

Question

Je ne comprends pas comment puis-je résoudre cet exercice.

J'ai besoin de créer une grammaire sans contexte qui puisse valider l'entrée suivante:

L={w € (0,1,2)* | w= 2^n 0^(m+1) 1^(m+n) with n>=0, m>0}

Comment puis-je créer le PDA correspondant?

Je pense que le langage n'a pas de propriété prefix donc le PDA ne peut pas accepter par pile vide. C'est vrai?

Answer 1

Essayons d'abord la grammaire; puis nous en ferons un automate.

Lors de la création d'un CFG - n'importe quelle grammaire, en fait, y compris les expressions régulières - il est utile de connaître quelques types de langages simples que la grammaire pourrait facilement utiliser. Les grammaires sans contexte peuvent facilement faire tout ce qu'une grammaire régulière peut faire, et elles peuvent également correspondre aux entrées. Cela signifie que les langages comme a ^ n b ^ n, les palindromes, les parenthèses correspondantes, etc. sont faciles à faire.

Lorsque vous examinez un problème comme celui-ci, essayez de voir à laquelle de ces langues stéréotypées, le cas échéant, tout ou partie des chaînes de votre langue ressemble. Dans ce cas, il semble que nous ayons une variation sur a ^ n b ^ n; nous devons le faire deux fois pour effectuer l'ajout.

Commençons par 0 ^ (m + 1) 1 ^ m. Pouvons-nous faire un CFG pour cela? Et bien certainement; c'est pratiquement la même chose qu'un ^ n b ^ n. La voici:

S := 0E
E := 0E1 | -

Nous devons maintenant aborder le terme n: nous devrions pouvoir ajouter 2 à gauche et 1 à droite, en nombre égal. C'est aussi simple:

S := 2S1 | S'
S' := 0E
E := 0E1 | -

Et voilà. Pour obtenir un CFG, vous pouvez facilement créer un analyseur ascendant ou descendant, selon la définition de ces choses. Nous allons essayer de créer un PDA à partir de zéro.

Notre PDA doit accepter 2 dans une boucle, en poussant chaque 2 sur la pile. Nous devrons nous rappeler combien nous en avons vu, après tout. Lorsque nous voyons un 0, nous devrions passer à un nouvel état et continuer à accepter 0 dans une boucle, en ajoutant un 0 à la pile pour chaque 0 vu en entrée. Lorsque nous voyons un 1, nous devrions passer à un nouvel état et accepter 1 dans une boucle, en supprimant 2 ou 0 de la pile. Si vous obtenez les bons détails de mise en œuvre, vous pourrez accepter avec une pile vide dans un état d'acceptation distinct des trois premiers.