(One Counter Languages)
Ein Zählautomat (one counter automaton) ist ein Kellerautomat, mit der Eigenschaft, dass das Kelleralphabet auSSer \( Z_{0} \) nur ein weiteres Symbol enthält. Damit kann der Automat zählen: er kann unterscheiden, ob der Zähler 0 oder nicht ist. Die Arbeitsweise des Automaten hängt also vom aktuellen Zustand, dem gelesenen Symbol, und ob der Zähler 0 oder ungleich 0 ist, ab. In jedem Schritt kann der Automat den Zustand wechseln und den Zähler um 1 inkrementieren bzw. dekrementieren, wobei letzteres nur erlaubt ist, wenn der Zähler ungleich 0 ist. Wir betrachten ein zweielementiges Alphabet \( \Sigma=\{a, b\} \).
(a) Geben Sie ein formales Modell des Zählautomaten an, analog zu dem eines Kellerautomaten und zeigen Sie, daSS der Zählautomat echt mächtiger ist als ein endlicher Automat.
(b) Ist ein Zählautomat genauso mächtig wie ein Kellerautomat? Geben Sie eine ausführliche Begründung für Ihre Antwort. (Hinweis: Betrachten Sie hierzu die Sprache \( \left\{w=w^{R}: w \in\{a, b\}^{+}\right\} \).)
(c) Erweitern Sie den Zählautomaten um einen zweiten Zähler. Ist dieses modifizierte Modell echt mächtiger als ein Zählautomat mit nur einem Zähler, oder sogar mächtiger als ein Kellerautomat?
Text erkannt:
Aufgabe 5 (0 Punkte, Extra (15 Punkte) (One Counter Languages))
Ein Zählautomat (one counter automaton) ist ein Kellerautomat, mit der Eigenschaft, dass das Kelleralphabet auSSer \( Z_{0} \) nur ein weiteres Symbol enthält. Damit kann der Automat zählen: er kann unterscheiden, ob der Zähler 0 oder nicht ist. Die Arbeitsweise des Automaten hängt also vom aktuellen Zustand, dem gelesenen Symbol, und ob der Zähler 0 oder ungleich 0 ist, ab. In jedem Schritt kann der Automat den Zustand wechseln und den Zähler um 1 inkrementieren bzw. dekrementieren, wobei letzteres nur erlaubt ist, wenn der Zähler ungleich 0 ist. Wir betrachten ein zweielementiges Alphabet \( \Sigma=\{a, b\} \).
(a) Geben Sie ein formales Modell des Zählautomaten an, analog zu dem eines Kellerautomaten und zeigen Sie, daSS der Zählautomat echt mächtiger ist als ein endlicher Automat.
(b) Ist ein Zählautomat genauso mächtig wie ein Kellerautomat? Geben Sie eine ausführliche Begründung für Ihre Antwort. (Hinweis: Betrachten Sie hierzu die Sprache \( \left\{w=w^{R}: w \in\{a, b\}^{+}\right\} \).)
(c) Erweitern Sie den Zählautomaten um einen zweiten Zähler. Ist dieses modifizierte Modell echt mächtiger als ein Zählautomat mit nur einem Zähler, oder sogar mächtiger als ein Kellerautomat?
Text erkannt:
Aufgabe 5 (0 Punkte, Extra (15 Punkte) (One Counter Languages))
Ein Zählautomat (one counter automaton) ist ein Kellerautomat, mit der Eigenschaft, dass das Kelleralphabet auSSer \( Z_{0} \) nur ein weiteres Symbol enthält. Damit kann der Automat zählen: er kann unterscheiden, ob der Zähler 0 oder nicht ist. Die Arbeitsweise des Automaten hängt also vom aktuellen Zustand, dem gelesenen Symbol, und ob der Zähler 0 oder ungleich 0 ist, ab. In jedem Schritt kann der Automat den Zustand wechseln und den Zähler um 1 inkrementieren bzw. dekrementieren, wobei letzteres nur erlaubt ist, wenn der Zähler ungleich 0 ist. Wir betrachten ein zweielementiges Alphabet \( \Sigma=\{a, b\} \).
(a) Geben Sie ein formales Modell des Zählautomaten an, analog zu dem eines Kellerautomaten und zeigen Sie, daSS der Zählautomat echt mächtiger ist als ein endlicher Automat.
(b) Ist ein Zählautomat genauso mächtig wie ein Kellerautomat? Geben Sie eine ausführliche Begründung für Ihre Antwort. (Hinweis: Betrachten Sie hierzu die Sprache \( \left\{w=w^{R}: w \in\{a, b\}^{+}\right\} \).)
(c) Erweitern Sie den Zählautomaten um einen zweiten Zähler. Ist dieses modifizierte Modell echt mächtiger als ein Zählautomat mit nur einem Zähler, oder sogar mächtiger als ein Kellerautomat?
