Construire un PDA pour le complément d'

16

Je me demande si cela est encore possible, puisque {anbncnn0}CFL . Par conséquent, un PDA qui peut distinguer un mot w{anbncnn0} du reste de {abc} pourrait aussi bien l'accepter, ce qui me semble contradictoire.

Je suppose que je dois profiter de la nature non déterministe des PDA, mais je suis à court d'idées. Si vous pouviez offrir quelques conseils, je l'apprécierais beaucoup.

hauptbenutzer
la source
Point intéressant à ce sujet qui semble contradictoire. En effet, les langues sans contexte ne sont pas fermées en prenant le complément ... il y a donc beaucoup d'exemples de langues sans contexte qui pourraient être "acceptées" dans le sens où vous y faites allusion. Je ne suis pas un théoricien et, en tant que tel, je ne peux pas vraiment concilier cela, mais peut-être que quelqu'un d'autre peut expliquer pourquoi ce n'est pas quelque chose à craindre?
Patrick87
A noter que cela généralise: le complément de est un CFG. {anbncndnen}
sdcvvc
Question similaire .
Raphael

Réponses:

15

Non, c'est sans contexte. Pour accepter , vous devez vous assurer que trois nombres sont égaux. Pour accepter a b c a n b n c n , il vous suffit de vous assurer que vous vous trouvez dans l'un des trois cas suivants:anbncnabcanbncn

  1. Le nombre de s est différent du nombre de b s; ouab
  2. Le nombre de s est différent du nombre de c s; ouac
  3. Le nombre de s est différent du nombre de c s.bc

Écrivez un PDA pour chacun de ces cas, puis combinez-les en passant de façon non déterministe à chacun à partir de l'état de départ.

Patrick87
la source
J'avais bien noté ces cas, mais l'idée de les connecter me manquait. Je vous remercie!
hauptbenutzer
4
En fait, vous n'avez besoin que de deux cas.
sdcvvc
@sdcvvc Bon point. :)
Patrick87
Pour un nombre différent de caractères, considérez ceci comme une inspiration: . Il devrait être simple de coller un + sur la gauche de celui-ci ou un c + sur la droite et de le transformer en PDA. Pour le cas délicat (dont vous n'avez pas besoin) S a S c | A | C ; A a B aSxSy|X|Y;Xx|xX;Yy|yYa+c+SaSc|A|C;AaB|aA;CBc|Cc;Bε|bB