Wie konsturiere ich einen Kellerautomaten

Question

Für ∑ = {a,b} sei die Sprache L:={w∈∑* | Anzahl der as in w = Anzahl der bs in w}

a)

Konstuieren Sie einen Kellerautomat, der L erkennt.

b)

Ist der konstruierte Kellerautomat deterministisch?

Gibt es einen deterministischen Kellerautomat, der L erkennt?

Answer 1

a) Wenn ein a gelesen wird und oben im Keller ein b liegt, dann wird es entfernt.

Wenn ein a gelesen wird und oben im Keller ein a liegt, dann wird ein a zum Keller hinzugefügt.

Wenn ein a gelesen wird und der Keller leer ist, dann wird ein a zum Keller hinzugefügt.

Lesen von b wird analog behandelt.

Der Kellerautomat akzeptiert wenn der Keller am Ende leer ist.

b) Der konstruierte Kellerautomat ist deterministisch.