+1 Daumen
457 Aufrufe

Betrachten Sie das Alphabet Σ = {a, b} und unten stehende Ausdrücke α, β und γ. Geben Sie für jeden Ausdruck an, ob er ein korrekter regulärer Ausdruck ist. Begründen Sie Ihre Antwort.


• α = ∅
• β = (a ∣ b)*
• γ = (a + ab)b^2a*

Avatar von

1 Antwort

+2 Daumen
 
Beste Antwort

Ohne eure Definition von regulären Ausdrücken, kann nur gemutmaßt werden.

α = ∅

\(\alpha\) ist ein regulärer Ausdruck über \(\Sigma\). Das folgt aus der Definition.

β = (a ∣ b)*

\(\omega_1:=a\) und \(\omega_2:=b\). \(\beta\) ist ein regulärer Ausdruck über \(\Sigma\), denn wenn \(\omega_1\) und \(\omega_2\) reguläre Ausdrücke über \(\Sigma\) sind, so sind auch \((\omega_1\mid \omega_2)\) ein regulärer Ausdruck. Wenn \(w_3\) ein regulärer Ausdruck ist, dann ist auch \(\omega_3^*\). Unter diesen Voraussetzungen ist \(\beta\) mit \(\omega_3:=(a\mid b)\) ein regulärer Ausdruck.

γ = (a + ab)b2a*

Das ist kein regulärer Ausdruck! Die Begründung ergibt sich direkt aus eurer Definition.

Avatar von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community