0 Daumen
292 Aufrufe

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

Avatar von

1 Antwort

0 Daumen
  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.
Avatar von 5,6 k

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

Ein anderes Problem?

Stell deine Frage

Ähnliche Fragen

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community