0 Daumen
749 Aufrufe

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?

von

1 Antwort

+1 Daumen
 
Beste Antwort

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.

von 5,5 k

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community