Mengenformulierung richtig?

18.10.2008, 20:00

NeedNoNick

Mengenformulierung richtig?

Sind meine Mengenumformulierungen richtig? Könnten Sie leichter
oder gar komplizierter sein? Vielleicht kann mir das ein
Mengen-formalitäts-Guru beantworten smile

Hinweis:
w und v sind keine Elemente sondern Wörter (theoretische Informatik)
und somit also Mengen. "." ist der Konkatenator ("Buchstabenverbinder").

Das Alphabet für 1) und 2): $\begin{eqnarray*} \Sigma = \{0,1\} \\ \end{eqnarray*}$

Die ursprüngliche Mengeformulationen der DEA Automaten-Sprache L(A1) & L(A2) lauten:

1)

L(A_1) := { w € Sigma* | w enthält eine ohne Rest durch 3 teilbaren Anzahl von Einsen}

Meine Umformulierung:

$\begin{eqnarray*} L(A_1) := \{ w \in \Sigma^{*} \> |\>\> |\{ v \subseteq w | \forall v_{n, 0<n\leq|w|}: v \in \Sigma \backslash \{0\}\}| \mod 3 = 0 \} \end{eqnarray*}$

2)

L(A_2) := { w € Sigma* | w enthält mindestens eine Eins und eine gerade Anzahl von Nullen folgt der letzten Eins }

Meine Umformulierung:

$\begin{eqnarray*} L(A_2) := \{w \in \Sigma^{*} \>| \>\> |w\backslash\{0\}|\geq 1, w = v.1.z, |z| \mod 2 = 0 \} \end{eqnarray*}$

18.10.2008, 23:02

kiste

Auf diesen Beitrag antworten »

Hallo,

das sieht ziemlich schrecklich aus Augenzwinkern

Es gibt 2 Möglichkeiten:
- Du benutzt reguläre Ausdrücke zum beschreiben der Sprache.
- Du versuchst es nochmal Augenzwinkern

Ich würde folgendes definieren: $\begin{eqnarray*} |w|_1 \end{eqnarray*}$ beschreibt die Anzahl der Einsen in w, analog $\begin{eqnarray*} |w|_0 \end{eqnarray*}$

Dann musst du so Dinge wie $\begin{eqnarray*} w\setminus \{0\} \end{eqnarray*}$ nicht machen Augenzwinkern

18.10.2008, 23:09

NeedNoNick

Auf diesen Beitrag antworten »

Ist |w|_1 als Summe der 1er Elemente der Wortmenge w
in der Mathematik allgemein gültig?
Denn ich möchte es nur allgemein mathematisch in einer
Zeile formulieren ohne extra (selbst erfundene) Angaben.
Allerdings klappt das mit dem ersten Tipp nicht,
also den Regulären Ausdrücken, da das in der
Mengenschreibweise nicht erlaubt ist.
Mit regulären Ausdrücken wäre das ganze natürlich einfacher,
aber ich wollte es eben in der üblichen Mengenschreibweise.
Trotzdem danke smile

Hat vielleicht sonst noch jemand Vorschläge? :-)

18.10.2008, 23:18

kiste

Auf diesen Beitrag antworten »

In der Mathematik werden selten Wörter betrachtet. Und gültig ist alles was wohldefiniert ist! Ich empfinde es als schön und einfach und immerhin benutzt es der Schöning(Standardwerk für theoretische Informatik) auch Augenzwinkern

18.10.2008, 23:27

papahuhn

Auf diesen Beitrag antworten »

NeedNoNick, wie habt ihr Wörter überhaupt definiert? Anscheinend als Mengen? Wie genau?

18.10.2008, 23:40

NeedNoNick

Auf diesen Beitrag antworten »

Du hast recht, eigentlicht sieht das da oben von mir wirklich hässlich aus geschockt

Hm, mein ehemaliger theoretische Mathematik Professor hat da was anderes,
also dass man Mengenschreibweise und reg.Expr. trennen muss.
Habs jetzt nochmal "umüberlegt"... was meint ihr dazu... mathematisch korrekt?:

1) L(A_1) := { w € Sigma* | w enthält eine ohne Rest durch 3 teilbaren Anzahl von Einsen}

Meine (neue) Umformulierung:
$\begin{eqnarray*} L(A_1) := \{ w\in \Sigma^{*}\>|\>\> | w \cap \{1\}| \mod 3 = 0 \} \end{eqnarray*}$

2) L(A_2) := { w € Sigma* | w enthält mindestens eine Eins und eine gerade Anzahl von Nullen folgt der letzten Eins }

Meine (neue) Umformulierung:
$\begin{eqnarray*} L(A_2) := \{ w\in \Sigma^{*}\>|\>\>\> (| w \cap \{1\}| \geq 1) \> , \> (\> w=v.1.u, \> |u\in\{0\}| \mod 2=0) \} \end{eqnarray*}$

Richtig oder? Oder müsste ich $\begin{eqnarray*} u\in\{0\} \end{eqnarray*}$ gesondert anschreiben
und mit Beistrich danach $\begin{eqnarray*} |u| \mod 2=0 \end{eqnarray*}$ ?

Warum bekomm ich vor dem "mod" immer so einen großen Abstand?
Gibts ne Alternative?

18.10.2008, 23:50

NeedNoNick

Auf diesen Beitrag antworten »

@papahuhn

$\begin{eqnarray*} Wort = endliche \> Folge \> von \> Symbolen \\ Alphabet \> \Sigma := \{a_1,a_2,...,a_n\}\\ |\Sigma|<\infty, zB: \Sigma=\{0,1\} \\ Wort \> w := w_1,w_2,...,w_n \\ w_i \in \Sigma \\ Konkatenation \> (Zusammenschluss): u = w.v \end{eqnarray*}$

18.10.2008, 23:59

kiste

Auf diesen Beitrag antworten »

Nein ist nicht korrekt, was soll den der Schnitt eines Wortes mit einem Buchstaben sein? Wenn du stattdessen meine Funktion nehmen würdest, passt es Augenzwinkern

19.10.2008, 10:39

NeedNoNick

Auf diesen Beitrag antworten »

"Nein es ist nicht korrekt."

Warum ist es nicht korrket? Wegen der Notation, dass ich das "w" nicht als
Menge nehmen sollte? Es ist ja eigentlich eine Folge, aber keine mathematische,
da sie ja keine feste ist sondern an Stelle i des Wortes jeder Buchstabe des
Alphabets stehen könnte.

Würde dann das also mathematisch (ohne erfundene Eigendefinitionen) stimmen?:

$\begin{eqnarray*} L(A_2) := \{ w\in \Sigma^{*}\>|\>\>\> (|w|_1 \geq 1) \> , \> (\> w=v.1.u, \> |u|_0 \mod 2=0) \} \end{eqnarray*}$

Mein Problem ist, dass wenn ich |w|_1 sehe an "zur Basis 1" oder "Index 1" aber
mir nicht ganz denken kann "alle 1er Elemente der Folge w". Gibt es im Internet
irgendwo ein Definitionsbeispiel für "alle (bestimmte) Zeichen des Wertes x einer
Folge w"? Oder müsste ich vielleicht eine Äquivalenzklasse über w legen?

"Was soll den der Schnitt eines Wortes mit einem Buchstaben sein?"

Einzelner Schritt mit Buchstabe: $\begin{eqnarray*} \delta(q,a)=p \end{eqnarray*}$
Mehrere Schritte mit Wort zum Endzustand: $\begin{eqnarray*} \delta^{*}(q,w)=p \in F \end{eqnarray*}$

Konstellation: $\begin{eqnarray*} \delta : Q \times \Sigma \Rightarrow Q \end{eqnarray*}$

$\begin{eqnarray*} \delta \end{eqnarray*}$ = Übergangsfunktion
q = Zustand, p = Folgezustand, F = Menge der Endzustände

19.10.2008, 10:53

kiste

Auf diesen Beitrag antworten »

Zitat:

Original von NeedNoNick
$\begin{eqnarray*} L(A_2) := \{ w\in \Sigma^{*}\>|\>\>\> (|w|_1 \geq 1) \> , \> (\> w=v.1.u, \> |u|_0 \mod 2=0) \} \end{eqnarray*}$

So hätte ich es gemacht, auch wenn das $\begin{eqnarray*} (|w|_1 \geq 1) \end{eqnarray*}$ nicht benötigt wird.
Genauer:
$\begin{eqnarray*} L(A_2) := \{ w\in \Sigma^{*}\>|\>\>\>\exists u\in \{0\}^*\exists v\in\Sigma^*: w=v.1.u, \> |u|_0 \mod 2=0\} \end{eqnarray*}$
Du hast anscheinend noch große Hemmungen etwas neu zu definieren. Das passiert jedoch in der Mathematik ständig. Wirklich festgelegt sind nur die grundlegenden Symbole darüberhinaus ist alles eigenständige Definition. Wenn du mal in ein Buch hineinschaust so gibt es immer eine Seite die die Bezeichner erklärt!

Ein Beispiel für ein Buch dass die Bezeichnung auch benutzt hab ich bereits geliefert, eine Internetseite finde ich jetzt auf die schnelle nicht.

"Was soll den der Schnitt eines Wortes mit einem Buchstaben sein?"
Hast du immer noch nicht erklärt, das was du hier hast ist die (nicht vollsändige) Beschreibung eines DFA.
Was ich mit der Frage ausdrücken wollte ist klar:
Ein Wort ist eine Folge von Buchstaben, es ist nicht definiert was der Schnitt eines Wortes mit einer Menge ist.

21.10.2008, 14:15

NeedNoNick

Auf diesen Beitrag antworten »

@ Kiste, danke smile

"Hast du immer noch nicht erklärt, das was du hier hast ist die
(nicht vollsändige) Beschreibung eines DFA."

Link: Deterministischer Endlicher Automat

Genauer könnte ich es auch nicht erklären

Neue Frage »

Antworten »

Mengenformulierung richtig?

Verwandte Themen