mehrere Kellerzeichen gleichzeitig löschen?

Question

Ist es möglich mehrere Kellerzeichen in einem Schritt/Übergang zu löschen?
 

Könnte ist also zb (s0, 0, ko) -> (s0, 0ko)
​                              (s0, 0, 0) -> (s1, 00)
​                              (s1, 1, 00) -> (s1, k0)

​also Übergänge definieren?

Answer 1

Hallo, 

Schauen wir uns hierfür ein Teil der Definition aus dem Lehrbuch an (S.49-50):

"Wenn sich der Kellerautomat in Zustand s ∈ S befindet und auf dem Eingabeband e gelesen wird und das oberste Kellerzeichen k ∈ K ist, dann wird k im Keller durch das ganze Wort v ∈ K* ersetzt, indem dieses von hinten nach vorne zeichenweise auf den Keller gepusht wird".

Desweiteren gilt für die Zustandsüberführungsfunktion folgendes:

δ∶ S × (E ∪ {λ}) × K → S × K*

Da der Lese/Schreibe-Kopf des Kellers immer auf dem obersten Kellerzeichen steht und nur dieses liest, sind nur Zustandsübergänge folgender Form erlaubt:

δ(s, e, k) = (s ′ , v)    mit s, s' ∈ S, e ∈ E, k ∈ K und v ∈ K*.

k besitzt daher nur ein Element aus K (und nicht wie du es angeben wolltest zwei Elemente (00). 

Zusammenfassend können wir also sagen, dass pro Rechenschritt jeweils nur das oberste Zeichen des Kellers überschrieben bzw. gelöscht werden kann. 

 

Ich hoffe ihr konnte dir damit weiterhelfe.

 

LG Tutor