Es gibt eine Sprache L = {0,1}^* und die Sache ist, dass 1 und 0 nicht von der gleichen Anzahl sein sollen. Wie kann ich das in einem PDA-Automaten präsentieren?Pushdown-Automation mit ungleichen Elementen
Vielen Dank im Voraus!
Ein PDA kann Eingaben lesen, auf einen Stapel schieben und von einem Stapel abspringen. Wenn ich versuche, Automaten, insbesondere PDAs und TMs, zu entwerfen, denke ich gerne an Input-Strings, bei denen lange Reihen von farbigen Murmeln oder Chips auf einem Tisch aufgereiht sind. Die Frage ist dann, wie kann man mit nur einem Stapel und Aufnehmen von Chips von links nach rechts feststellen, ob eine Reihe von Chips eine unterschiedliche Anzahl von roten und blauen Chips hat?
Eine Methode ist die folgende. Wenn du eine Murmel einsammelst, sieh dir den Stapel an. Wenn der Stapel leer ist oder oben den gleichen Farbchip hat, lege deinen Chip ab. Wenn der oberste Chip eine andere Farbe hat, wirf den Chip, den du aufgehoben hast, und den obersten Chip vom Stapel in einen Beutel. Fahren Sie fort, bis Sie alle Chips abgeholt haben. Jetzt schau auf den Stapel. Wenn der Stapel leer ist, bedeutet das, dass Sie die gleiche Anzahl roter und blauer Chips weggeworfen haben müssen. Wenn Sie Chips im Stapel haben, bedeutet das, dass es Chips gab, die Sie nicht wegwerfen konnten. In der Tat sagt Ihnen die Farbe der verbleibenden Chips, um welche Art von Chip es sich handelt.