reguläre ausdrücke...

[mathik]

hallo leute!

ich habe da ein paar grundlegende fragen zu regulären ausdrücken...

sei Λ und r ein regulärer ausdruck.
Λ erkennt die sprache L(Λ) = {}.

was ist dann L(Λr)?
ist es die leere menge? oder {ε}

ich würde sagen die leere menge...

sei A ein alphabet.
ist A⁰ = {ε} ?

denn das würde erklären, warum gilt:
Λ* = ε

ich kann diese aufgabe einfach nicht lösen

sei r und s ein regulärer ausdruck, man gebe x an so dass gilt:

x = rx + s

danke!

Gruß mathik

[Gast]

Hi

Bin mir nicht sicher ob wir unter + das gleiche Verstehen.
Für gewöhnlich ist + ein unärer Operator und definiert als r+ = rr* wobei r ein regulärer Ausdruck ist.
Du benutzt ihn aber derart, dass r+s der Menge "L(r) vereinigt L(s)" entspricht. Korrekt?

Wenn ja, hier eine Lösung für 3. (wobei ich | statt + verwende)

x = (rr*s|s)

Das entspricht den Ausdrücken
s,
rs,
rrs,
rrrs,
...

Eingesetzt in die rechte Seite von
x = rx|s
ergibt sich

r(rr*s|s)|s = rrr*s|rs|s womit sich ebenfalls die Ausdrücke
s,
rs,
rrs,
rrrs,
...

erzeugen lassen.

Die anderen Aufgaben kannst du selbst mit den Definitionen lösen.

space

[mathik]

hallo space!

danke für die hilfe.

also zu 1. würde ich sagen, es ist die leere menge, weil:
{} x L(r) = {}

zu 2:

ich weiß das A* = A⁰ V A¹ V ... V Aⁿ
V = "vereinigung"
und ich weiß dass A⁺ = A x A* = A¹ V ... V Aⁿ = A* - {ε}
also ist dann wohl A⁰ = {ε}
ist das eine definition?

zu 3:

also für x = (r*s + s) geht das wohl auch... (+ ist bei uns das oder)

aber wie kommt man auf sowas?

danke!

Gruß mathik

[Gast]

Hallo

mathik schrieb:

hallo space!

danke für die hilfe.

also zu 1. würde ich sagen, es ist die leere menge, weil:
{} x L(r) = {}

Vorsicht mit der Schreibweise. Das "x" sieht stark nach einem karthesischen Produkt aus, hat aber nichts damit zu tun.
Ansonsten, ja es ist die leere Menge.
Es gilt AB = { ab | a ist in A und B ist in B } für bel. Mengen A und B.
Das ist die Definition der Kontakenation zweier Mengen.
Nun sei A leer. Die Bedingung "a ist in A" kann nicht erfüllt werden also ist auch AB leer.

mathik schrieb:

zu 2:

ich weiß das A* = A⁰ V A¹ V ... V Aⁿ
V = "vereinigung"
und ich weiß dass A⁺ = A x A* = A¹ V ... V Aⁿ = A* - {ε}
also ist dann wohl A⁰ = {ε}
ist das eine definition?

Auch korrekt, A⁰ = {ε}.
In deiner Gleichungskette
A⁺ = AA* = A* - {ε}
ist trotzdem ein Fehler.
Wenn nämlich ε ein Element von A ist, dann ist es auch Element von A⁺.
D.h. ist ε Element von A, dann ist A⁺ = A^* und A⁺ = A^* - {ε} wäre falsch.

mathik schrieb:

zu 3:

also für x = (r*s + s) geht das wohl auch... (+ ist bei uns das oder)

aber wie kommt man auf sowas?

Oh stimmt, das ist sogar noch besser (weil kürzer :))
Ein Rezept um auf sowas zu kommen kenne ich nicht. Einfach ein wenig drüber nachdenken dann ergibt sich sowas meist von alleine.

mathik schrieb:

danke!

Gruß mathik

Bitte, space

[mathik]

wir haben worte zu einem Alphabet A über folgen definiert:
s: {1, 2, ... , n} -> A

und die menge aller folgen der länge n ist bis auf umbennung gleich Aⁿ, da eine bijektive funktion zwischen den beiden mengen existiert.
und Aⁿ ist das n-fache kartesische produkt von A.

deswegen sollte doch das korrekt sein:
A⁺ = A x A^* = A x (A⁰ V A¹ V ... V Aⁿ)
= A¹ V ... V Aⁿ⁺¹ = A^* - A⁰ = A^* - {ε}

und wieso soll ε in A sein?

Gruß mathik

[Gast]

Es gilt
$A^* = \cup_{i=0}^{\infty} A^i$
und
$A^+ = \cup_{i=1}^{\infty} A^i$

Also Wörter NICHT nur bis Länge n, sondern bis zu einer beliebigen aber endlichen Länge.

Außerdem wirfst du glaub ich zwei Dinge durcheinander.
Zum einen den Exponentationsoperator (via verallgemeinerter Konkatenation auf dem Monoid)
$A^n = A^{n-1}A , A^0 = \{\epsilon\}$
und zum anderen das n-fache Karthesische Produkt, ebenfalls mit A^n bezeichnet, für Mengen.

Wie auch immer.
Es gilt
$\epsilon \in A \Leftrightarrow A^+=A^*$

Beweis:

$\Rightarrow$
Sei
$\epsilon \in A$
Dann gilt
$A^1=A \Rightarrow \epsilon \in \cup_{i=1}^{\infty} A^i = A^+$
Also gilt
$A^+ = A^+ \cup \{\epsilon\} = A^+ \cup A^0 = \cup_{i=0}^{\infty} A^i = A^*$

$\Leftarrow$
Sei
$A^+=A^*$
Also
$\cup_{i=1}^{\infty} A^i = \cup_{i=0}^{\infty} A^i$
Weiter
$A^0 = \{\epsilon\} \Rightarrow \epsilon \in A^+ \Rightarrow \epsilon \in A$

q.e.d.

So, und damit ist
$A^+ = A^* - \{\epsilon\}$
nicht allgemeingültig und nur genau dann wahr, wenn
$\epsilon \notin A$

wieso soll ? in A sein?

Wieso sollte es nicht in A sein ?
Es hängt ja wohl nur von der Aufgabenstellung ab, ob das leere Wort in der gegebenen Sprache liegt oder nicht.

Gruß, space

[mathik]

space schrieb:

Es gilt
$A^* = \cup_{i=0}^{\infty} A^i$
und
$A^+ = \cup_{i=1}^{\infty} A^i$

Also Wörter NICHT nur bis Länge n, sondern bis zu einer beliebigen aber endlichen Länge.

ich meinte mit n natürlich auch unendlich. ist sicherlich nicht ganz sauber wie ich das aufgeschrieben habe, mit n und n + 1 . meinte damit aber ∞ und ∞ + 1 = ∞

space schrieb:

Außerdem wirfst du glaub ich zwei Dinge durcheinander.
Zum einen den Exponentationsoperator (via verallgemeinerter Konkatenation auf dem Monoid)
$A^n = A^{n-1}A , A^0 = \{\epsilon\}$
und zum anderen das n-fache Karthesische Produkt, ebenfalls mit A^n bezeichnet, für Mengen.

ich weiß nicht genau, was du damit genau meinst (mit "Exponentationsoperator").
allerdings ist doch die sprache L(a*) = A*.
und A* ist ja eine Menge:
$A^* = \cup_{i=0}^{\infty} A^i = A^0 \cup A^1 \cup A^2 ...$
was soll denn das $A^i$ hier denn bedeuten, wenn nicht das kartesische produkt

space schrieb:

Wie auch immer.
Es gilt
$\epsilon \in A \Leftrightarrow A^+=A^*$

Beweis:

$\Rightarrow$
Sei
$\epsilon \in A$
Dann gilt
$A^1=A \Rightarrow \epsilon \in \cup_{i=1}^{\infty} A^i = A^+$
Also gilt
$A^+ = A^+ \cup \{\epsilon\} = A^+ \cup A^0 = \cup_{i=0}^{\infty} A^i = A^*$

$\Leftarrow$
Sei
$A^+=A^*$
Also
$\cup_{i=1}^{\infty} A^i = \cup_{i=0}^{\infty} A^i$
Weiter
$A^0 = \{\epsilon\} \Rightarrow \epsilon \in A^+ \Rightarrow \epsilon \in A$

q.e.d.

So, und damit ist
$A^+ = A^* - \{\epsilon\}$
nicht allgemeingültig und nur genau dann wahr, wenn
$\epsilon \notin A$

wieso soll ? in A sein?

Wieso sollte es nicht in A sein ?
Es hängt ja wohl nur von der Aufgabenstellung ab, ob das leere Wort in der gegebenen Sprache liegt oder nicht.

das leuchtet ein, aber warum sollte ε in A sein?
was wäre dann das neutrale element?

vielleicht sollte ich den beweis für $\lambda^* = \epsilon$
so führen:
sei $\epsilon \in L(\lambda^*)$
$\Leftrightarrow \epsilon \in \emptyset^0 = \{\epsilon\} \subseteq \emptyset^* = \cup_{i=0}^{\infty} \emptyset^i$