Kellerautomaten graphisch darstellen

Question

Frage:

Stellen Sie mit der hier eingeführten Notation die Kellerautomaten, die genau die nachfolgenden Sprachen akzeptieren, graphisch dar. Geben Sie außerdem für jeden der \( \mathrm{Au}- \) tomaten an, ob er deterministisch ist, und begründen Sie Ihre Aussage.
1. \( L=\left\{a^{m} b^{n} \mid m, n \in \mathbb{N} \wedge m \neq n\right\} \)
2. \( L=\left\{w a^{n}\left|n \in \mathbb{N} \wedge w \in\{a, b\}^{*} \wedge n=\right| w \mid\right\} \)
3. \( L=\left\{w w^{R} \in\{a, b\}^{*}|\exists n \in \mathbb{N}:| w \mid=2 n\right\} \)

Ich wäre sehr dankbar, wenn mir jemand weiterhelfen könnte!

LG

Answer 1

1. Die Sprache \(\left\{a^{m} b^{n} \mid m, n \in \mathbb{N}\right\}\) ist regulär. Zeichne den Automaten. Überlege dir, wie der Keller manipuliert werden muss, damit jedes Wort zusätzlich die Bedingung \(m \neq n\) erfüllt. Kann deterministisch gemacht weden.
   
2. Zuerst \(w\) lesen und für jeden gelesenen Buchstaben ein Symbol auf den Kellerspeicher legen. Dann \(a^n\) lesen und für jedes gelesene \(a\) ein Symbol vom Keller entfernen. Lieber nicht-deterministisch, weil man nicht weiß ob ein gelesenes \(a\) noch Bestandteil von \(w\) ist oder bereits von \(a^n\).
   
3. Wie 2. nur dass das Symbol auf dem Kellerspeicher beim Schreiben nicht beliebig ist und beim Lesen mit dem gelesenen Buchstaben des Wortes verglichen werden muss.

Comments

Hättest du einen Tipp, wie man m ungleich n graphisch darstellen kann? Leider komme ich nicht darauf

a / # / a#

a / a / aa

a / b / ab

b / # / b#

b / b / bb

b / a / ba

---

Wie sieht denn dein Automat aus.

a / # / a#

Ich weiß nicht, was das bedeutet.

---

"#" ist das Kellersymbol