CR und Konfluenz

• Def: CR: (←∪→)^*⊆(→^*⋅←^*)

• Def: Konfluenz: (←^*⋅→^*)⊆(→^*⋅←^*)

• Satz: diese Eigenschaften stimmen überein

  (deswegen nur eine gemeinsame Bezeichnung)

• Beweis: CR ⇒ Konfluenz wie eben (einfache Inklusion)

• B: Konfluenz ⇒ CR: Ind. nach k in →^*⋅(←^*⋅→^*)^k⋅←^*:

  einen Berg (←^*⋅→^*) durch ein Tal (→^*⋅←^*) ersetzen:

  →^*⋅(←^*⋅→^*)^k+1⋅←^*

    = →^*⋅(←^*⋅→^*)⋅(←^*⋅→^*)^k⋅←^*

  ⊆ →^*⋅(→^*⋅←^*)⋅(←^*⋅→^*)^k⋅←^*

  ⊆ →^*⋅(←^*⋅→^*)^k⋅←^*