1. Zeige, dass die (RE)MA eine TM simulieren können.
2. 👉 Zeige, dass die (RE)MA eine MA simulieren kann.
3. Zeige, wie aus jedem REMA ein äquivalener MA erstellt werden kann.

Ein MA ist rein REMA ohne reguläre Ausdrücke. Die Suche erfolgt ausschliesslich wortwörtlich (literally). Es sind reine typographisch Ersetzungsregeln. Markers sind allerdings erlaubt. Die Ergänzung der MA um RE erlaubt gewisse Dinge deutlich einfach zu erledigen, nun müssen wir aber darauf verzichten.

Beispiel: Füge am Ende der Eingabe über das Alphabeth Σ = {0, 1} eine 1 hinzu.

• Als REMA: /$/1/! und fertig
• Als einfache MA:

  /α1/1α/
  /α0/0α/
  /α/1/!
  //α/

Mangels Joker . und Gruppen (...) muss hier für jeden Buchstaben in Alphabet eine Regel angegeben werden wie das α ans Ende kommt. Ganz schön mühsam.

000000000ε
α1 → 1α
α0 → 0α
α  ¬ 1
ε  → α

eXECUTOR

/\n/Σ/g
/\s//g
/ΔΨ([^Σ]*Σ)(.*)Ψε→([^Σ]*)/ΔΨ$3$1Ψ$2ε→$3/
/ΔΨ([^Σ]*)(.*)(ΣΨε¬)([^Σ]*)/$4$1/ !
/Δ(.*?)(.+)Ψ([^Σ]*Σ)(.*)\2Ψ→(ε)/ΔΨ$1$3Ψ$4$2→$5/
/Δ(.*?)(.+)Ψ([^Σ]*Σ)(.*)\2Ψ¬(ε).*/$1/!
/Δ(.*?)(.+)Ψ([^Σ]*Σ)(.*)\2Ψ→([^Σ]*)/ΔΨ$1$5$3Ψ$4$2→$5/
/Δ(.*?)(.+)Ψ([^Σ]*Σ)(.*)\2Ψ¬([^Σ]*).*/$1$5/!
/Ψ([^Σ])(.*)Ψ\1/$1Ψ$2$1Ψ/ 
/Ψ([^Σ])(.*Σ)Ψ(.)/$1Ψ$2Ψ$3/
/Δ(.*)Ψ(.*[^Σ])Ψ(.*?Σ)/ΔΨ$1$2$3Ψ/
/Δ(.*)ΨΣ(.*)Ψ(.*?)Σ/ΔΨ$1Σ$2$3ΣΨ/
/Δ(.*)ΨΣ.*/$1/!
/(.*?)Σ/ΔΨ$1ΣΨ/