Gib einen Kellerautomaten an, der folgende Sprache akzeptiert:

´L = {a^m b^n in {a,b}^(**) | m >= n >= 0}´

Approach

Ein Kellerautomat ´M´ könnte folgendermaßen funktionieren:

Beim Lesen eines ´a´ wird ein ´A´ auf den Keller gelegt oder der Keller unverändert gelassen. Beim Lesen des ersten ´b´ wird der Zustand gewechselt. Im zweiten Zustand darf kein ´a´ mehr gelesen werden. Außerdem wird für jedes ´b´ ein ´A´ aus dem Keller gelöscht. Ist der Keller nach Einlesen des Eingabewortes leer, waren mindestens so viele ´a´s wie ´b´s im Wort.


Solution

  • ´M = ({s,f}, {a,b}, {A}, s, {s,f}, delta)´

    mit

    ´delta(s, a, #) = {(s, R, A), (s, R, lambda)}´ ´delta(s, a, A) = {(s, R, "AA"), (s, R, A)}´ ´delta(s, b, A) = delta(f, b, A) = {(f, R, lambda)}´ ´delta(s, b, #) = delta(f, b, #) = delta(f, a, #) = delta(f, a, A) = O/´

  • URL:
  • Language:
  • Subjects: theoretical computer science
  • Type: Name
  • Duration: 30min
  • Credits: 4
  • Difficulty: 0.6
  • Tags: hpi pushdown automaton
  • Note:
    HPI, 2014-04-26, Theoretische Informatik 2, Blatt 3, Aufgabe 2
  • Created By: adius
  • Created At:
    2014-07-21 19:07:42 UTC
  • Last Modified:
    2014-07-21 19:07:42 UTC