Construire un PDA pour le complément d'

Je me demande si cela est encore possible, puisque $\{a^n b^n c^n \mid n \geq 0\} \not\in \mathrm{CFL}$ . Par conséquent, un PDA qui peut distinguer un mot $w\in\{a^n b^n c^n \mid n \geq 0\}$ du reste de $\{a^*b^*c^*\}$ 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.

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:$a^nb^nc^n$$a^*b^*c^* \setminus a^nb^nc^n$

1. Le nombre de s est différent du nombre de b s; ou$a$$b$
2. Le nombre de s est différent du nombre de c s; ou$a$$c$
3. Le nombre de s est différent du nombre de c s.$b$$c$

É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.