Geben Sie für jeden Ausdruck an, ob er ein korrekter regulärer Ausdruck ist

Question

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*

Answer 1

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.