Lab

ein- und ausgabe. optimieren für anzahl schritte.

/αI{10}/Iα/g
/αI{9}ω/ω9/
/αI{8}ω/ω8/
/αI{7}ω/ω7/
/αI{6}ω/ω6/
/αI{5}ω/ω5/
/αI{4}ω/ω4/
/αI{3}ω/ω3/
/αI{2}ω/ω2/
/αI{1}ω/ω1/
/αω/ω0/
/(I+)ω?/α$1ω/
/ω//!

Input 454665122334
Output 111 (drei ringe aufbrechen)

Idee: Für jeden Ring entscheiden ob er aufgebrochen werden muss oder nicht. -> Binäres zählen

Teilproblem binäres zählen:  10001 -> 10010
/1β/β0/
/0?β/1/ !
/$/β/

Teilproblem Ringliste: 454665122334 -> 454665122334χ456123
/χ(.*)(.)(.*)\2/χ$1$2$3/
/χ/χ/! 
/.*/$&χ$&/ 

Teilproblem Prüfe Konfiguration: 454665122334:456123:110001 -> CLEAN/CONNECTED
hier würde 4, 5 und 3 aufgebrochen. 

/γ(.)(.*)ε0/γ$2ε/
/γ(.)(.*)ε1/$1γ$2ε/
/π(.)(.)(.*)φ(.*)\1(.*)γ/π$3φ$4$1$5γ/
/π(.)(.)(.*)φ(.*)\2(.*)γ/π$3φ$4$2$5γ/
/πφ.*/CLEAN/!
/π.*/CONNECTED/!
/(.*):(.*):(.*)/π$1φγ$2ε$3/

454665122334:456123B:110001 -> 454665122334:456123B:110001 

Ablaufsteuerung:

##########################################################

Phase A) Initialisierung: 122334 -> 1111ξ122334:1234:0000B

/A(.*)(.)(.*)\2(.*):/A$1$2$3$4:/
/(.*)A(.)(.*):/1$1$2A$3:0/ 
/(.*):(.*)A:(.*)/$1:$2:$3B/ 
/(.*)/ξ$1:A$1:/

##########################################################

Phase B) Prüfen der Konfiguration
Ringe noch verbunden -> Phase C   1111ξ122334:1234:0000B -> 1111ξ122334:1234:0000C
Ringe nicht verbunden -> Phase D  1111ξ122334:1234:0101B -> 1111ξ122334:1234:0101D

/γ(.)(.*)ε0/γ$2ε/
/γ(.)(.*)ε1/$1γ$2ε/
/B(.)(.)(.*)φ(.*)\1(.*)γ/B$3φ$4$1$5γ/
/B(.)(.)(.*)φ(.*)\2(.*)γ/B$3φ$4$2$5γ/
/Bφ.*/D/ 
/B.+/C/ 
/ξ(.*):(.*):(.*)B/ξ$1:$2:$3B$1φγ$2ε$3/

##########################################################

Phase C) Binäres zählen	& Schluss    1111ξ122334:1234:0011C -> 1111ξ122334:1234:0100B
                    falls am ENDE    11ξ122334:1234:1111C -> 11
/1C/C0/
/ξ.*:C.*//! 
/0?C(.*)/1$1B/ 

##########################################################

Phase D+E) Auswerten     1111ξ122334:1234:0101D -> 11ξ122334:1234:0111C

/E(.*)0/E$1/ 
/^(1*)(1*)ξ(.*)E\1$/$1ξ$3C/  
/E.*/C/ 
/([01]*)D/$1E$1/ 
 

##########################################################

/1C/C0/
/:C/ all tested /! 
/0?C(.*)/1$1B/

/γ(.)(.*)ε0/γ$2ε/
/γ(.)(.*)ε1/$1γ$2ε/
/B(.)(.)(.*)φ(.*)\1(.*)γ/B$3φ$4$1$5γ/
/B(.)(.)(.*)φ(.*)\2(.*)γ/B$3φ$4$2$5γ/
/Bφ.*/E/ !
/B.+/C/
/(.*):(.*):(.*)B/$1:$2:$3B$1φγ$2ε$3/

/A(.*)(.)(.*)\2(.*):/A$1$2$3$4:/
/A(.)(.*):/$1A$2:0/ 
/(.*):(.*)A:(.*)/$1:$2:$3B/  !
/(.*)/$1:A$1:/

Programm am Schluss

/E(.*)0/E$1/ 
/^(1*)(1*)ξ(.*)E\1$/$1ξ$3C/  
/E.*/C/

/([01]*)D/$1E$1/ 

/1C/C0/
/ξ.*:C.*//! 
/0?C(.*)/1$1B/ 

/γ(.)(.*)ε0/γ$2ε/
/γ(.)(.*)ε1/$1γ$2ε/
/B(.)(.)(.*)φ(.*)\1(.*)γ/B$3φ$4$1$5γ/
/B(.)(.)(.*)φ(.*)\2(.*)γ/B$3φ$4$2$5γ/
/Bφ.*/D/ 
/B.+/C/ 
/ξ(.*):(.*):(.*)B/ξ$1:$2:$3B$1φγ$2ε$3/

/A(.*)(.)(.*)\2(.*):/A$1$2$3$4:/
/(.*)A(.)(.*):/1$1$2A$3:0/ 
/(.*):(.*)A:(.*)/$1:$2:$3B/  
/(.*)/ξ$1:A$1:/

Quelle

Merge Intervals [en] ☆☆☆

Eingabe ex.

I:III,III:IIII,II:IIIIII,III:IIII

Ausgabe ex.

I:IIIIII

Lösung

/(I+)(I+):(I+),\1:(I+)/$1:$4,$1$2:$3/
/:(I+)(I*),I*:\1\b/:$1$2/
/:(I+)(I*),\1I?:/:/

Eingabe

# tape startzustand
□
# zustandsübergänge
q0, □ → q1, 1, R
q0, 1 → qf, 1, R
q1, □ → q2, □, R
q1, 1 → q1, 1, R
q2, □ → q2, 1, L
q2, 1 → q0, 1, L

Ausgabe

111111

Code

TM Simulator für Markow Algorithmen

# initialisierung
/^#.*\n//gm                                             kommentare entfernen 
/^([^τ])(.*)\n([^,]*)/τλ$1$2σ$3\n$3/
/\n([^,]*),([^→]*)→([^,]*),([^,]*),(.*)/δ$1ζ$2$4$5$3/g  regeln strukturieren
/\s//g                                                  leerschläge entfernen
/τλ/τ□λ/                                                blanks links hinzufügen
/λσ/λ□σ/                                                blanks rechts vom kopf

   1   2    3      4      5      6    
/λ(.)(.*)σ([^δ]+)(.*δ\3ζ\1(.)R([^δ]+))/$5λ$2σ$6$4/      r-regel anwenden

  1   2  3     4      5       6    7    
/(.)λ(.)(.*)σ([^δ]+)(.*δ\4ζ\2(.)L([^δ]+))/λ$1$6$3σ$7$5/ l-regel anwenden

/τ□*(.*)λ(.*?)□*σ.*/$1$2/!                              terminieren