Bemerkung zu Reg. Ausdr.

Wie beweist man w∈L(X) ?

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

• wenn X = X₁ + X₂ :

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

• wenn X = X₁⋅X₂ :

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

• wenn X = X₁^* :

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

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

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