M
space schrieb:
Es gilt
A∗=∪i=0∞AiA^* = \cup_{i=0}^{\infty} A^iA∗=∪i=0∞Ai
und
A+=∪i=1∞AiA^+ = \cup_{i=1}^{\infty} A^iA+=∪i=1∞Ai
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)
An=An−1A,A0={ϵ}A^n = A^{n-1}A , A^0 = \{\epsilon\}An=An−1A,A0={ϵ}
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∗=∪i=0∞Ai=A0∪A1∪A2...A^* = \cup_{i=0}^{\infty} A^i = A^0 \cup A^1 \cup A^2 ...A∗=∪i=0∞Ai=A0∪A1∪A2...
was soll denn das AiA^iAi hier denn bedeuten, wenn nicht das kartesische produkt
space schrieb:
Wie auch immer.
Es gilt
ϵ∈A⇔A+=A∗\epsilon \in A \Leftrightarrow A^+=A^*ϵ∈A⇔A+=A∗
Beweis:
⇒\Rightarrow⇒
Sei
ϵ∈A\epsilon \in Aϵ∈A
Dann gilt
A1=A⇒ϵ∈∪i=1∞Ai=A+A^1=A \Rightarrow \epsilon \in \cup_{i=1}^{\infty} A^i = A^+A1=A⇒ϵ∈∪i=1∞Ai=A+
Also gilt
A+=A+∪{ϵ}=A+∪A0=∪i=0∞Ai=A∗A^+ = A^+ \cup \{\epsilon\} = A^+ \cup A^0 = \cup_{i=0}^{\infty} A^i = A^*A+=A+∪{ϵ}=A+∪A0=∪i=0∞Ai=A∗
⇐\Leftarrow⇐
Sei
A+=A∗A^+=A^*A+=A∗
Also
∪i=1∞Ai=∪i=0∞Ai\cup_{i=1}^{\infty} A^i = \cup_{i=0}^{\infty} A^i∪i=1∞Ai=∪i=0∞Ai
Weiter
A0={ϵ}⇒ϵ∈A+⇒ϵ∈AA^0 = \{\epsilon\} \Rightarrow \epsilon \in A^+ \Rightarrow \epsilon \in AA0={ϵ}⇒ϵ∈A+⇒ϵ∈A
q.e.d.
So, und damit ist
A+=A∗−{ϵ}A^+ = A^* - \{\epsilon\}A+=A∗−{ϵ}
nicht allgemeingültig und nur genau dann wahr, wenn
ϵ∉A\epsilon \notin Aϵ∉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 ϵ∈L(λ∗)\epsilon \in L(\lambda^*)ϵ∈L(λ∗)
⇔ϵ∈∅0={ϵ}⊆∅∗=∪i=0∞∅i\Leftrightarrow \epsilon \in \emptyset^0 = \{\epsilon\} \subseteq \emptyset^* = \cup_{i=0}^{\infty} \emptyset^i⇔ϵ∈∅0={ϵ}⊆∅∗=∪i=0∞∅i
