Es sei folgender Kellerautomat gegeben:

´M = ({a, b}, {z_0, z_1}, {a}, z_0, {z_0}, delta)´

mit

´delta(z_0, a, #) = (z_0, R, a)´ ´delta(z_0, b, #) = (z_1, R, a)´ ´delta(z_0, a, a) = (z_0, R, aa)´ ´delta(z_0, b, a) = (z_0, R, lambda)´ ´delta(z_1, x, a) = (z_1, R, a) " für " x in {a, b}´

Bestimme die Sprache ´T(M)´.

Approach

Im Zustand ´z_0´ geschieht Folgendes: Beim Lesen von ´a´ wird zusätzlich ein ´a´ in den Keller gelegt. Ist im Keller mindestens ein ´a´ und wird ein ´b´ gelesen, so wird ein ´a´ im Keller gestrichen. Ist der Keller leer und wird ein ´b´ gelesen, so wird in ´z_1´ gewechselt. Der Zustand ´z_1´ wird nicht mehr verlassen, wodurch der Automat nicht mehr akzeptieren kann. Der Keller ist leer, wenn die gleiche Anzahl von ´a´s und ´b´s gelesen wurden.


Solution

  • ´T(M) = {w {:|:} |w|_a = |w|_b, |u|_a >= |u|_b " für jedes Präfix " u " von " w}´

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