Konstruieren Sie einen PDA für das Komplement von

Ich frage mich , ob dies überhaupt möglich ist, da . Daher könnte ein PDA, der ein Wort vom Rest von es genauso gut akzeptieren , was für mich widersprüchlich klingt.$\{a^n b^n c^n \mid n \geq 0\} \not\in \mathrm{CFL}${ a ∗ b ∗ c ∗$w\in\{a^n b^n c^n \mid n \geq 0\}$$\{a^*b^*c^*\}$

Ich denke, ich muss den nicht deterministischen Charakter von PDAs ausnutzen, aber mir fehlen die Ideen. Wenn Sie mir einen Rat geben könnten, wäre ich Ihnen sehr dankbar.

Nein, das ist kontextfrei. Um zu akzeptieren , müssen Sie sicherstellen, dass drei Zahlen gleich sind. So nehmen Sie eine * b * c * ∖ eine n b n c n , Sie müssen nur sicherstellen , dass Sie in einem der folgenden drei Fälle sind:$a^nb^nc^n$$a^*b^*c^* \setminus a^nb^nc^n$

1. Die Anzahl von s unterscheidet sich von der Anzahl von b s; oder$a$$b$
2. Die Anzahl von s unterscheidet sich von der Anzahl von c s; oder$a$$c$
3. Die Anzahl von unterscheidet sich von der Anzahl von cs .$b$$c$

Schreiben Sie für jeden dieser Fälle einen PDA und kombinieren Sie sie, indem Sie vom Startzustand aus nicht deterministisch zu jedem einzelnen springen.