Bemerkung zu Reg. Ausdr.

Wie beweist man w∈L(X) mathend000#?

(Wort w mathend000# gehört zur Sprache eines regulären Ausdrucks X mathend000#)

• wenn X = X₁ + X₂ mathend000#:

  beweise w∈L(X₁) mathend000# oder beweise w∈L(X₂) mathend000#

• wenn X = X₁⋅X₂ mathend000#:

  zerlege w = w₁⋅w₂ mathend000# und beweise w₁∈L(X₁) mathend000# und beweise w₂∈L(X₂) mathend000#.

• wenn X = X₁^* mathend000#:

  wähle einen Exponenten k∈$\mathbb {N}$ mathend000# und beweise w∈L(X₁^k) mathend000# (nach vorigem Schema)

Beispiel: w = abba, X = (ab^*)^* mathend000#.

w = abb⋅a = ab²⋅ab⁰∈ab^*⋅ab^*⊆(ab^*)²⊆(ab^*)^* mathend000#.