Gib einen Kellerautomaten an, der folgende Sprache akzeptiert:

´L = {w in {a, b}^(**) | w " hat ungerade Länge und das mittlere Symbol ist ein " a}´

Approach

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

Es wird akzeptiert, wenn das Wort nur aus einem ´a´ besteht, d.h. beim Lesen von ´a´ am Anfang kann in den akzeptierenden Zustand gewechselt werden. Hat das Wort mindestens die Länge ´3´, so wird im ersten Zustand die Länge der ersten Hälfte des Wortes auf den Keller gelegt, dann wird unter Lesen eines ´a´s in den zweiten Zustand gewechselt. Hier wird nun geprüft, dass genau so viele Buchstaben auf dem Keller liegen wie noch im Wort übrig sind.


Solution

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

    mit

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

  • URL:
  • Language:
  • Subjects: theoretical computer science
  • Type: Name
  • Duration: 30min
  • Credits: 4
  • Difficulty: 0.5
  • Tags: hpi pushdown automaton
  • Note:
    HPI, 2014-04-26, Theoretische Informatik 2, Blatt 3, Aufgabe 1
  • Created By: adius
  • Created At:
    2014-07-21 18:55:48 UTC
  • Last Modified:
    2014-07-24 17:26:16 UTC