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^*)^*.