Halbordung auf Alphabet

13.11.2011, 13:52	stefan90	Auf diesen Beitrag antworten »
Halbordung auf Alphabet Hallo, ich glaube ich stehe gerade ein bisschen auf dem Schlauch: Wenn gilt: $\begin{eqnarray} Q \subseteq \Sigma^ \times \Sigma^, \forall x,y \in \Sigma^: ( xQy :\Leftrightarrow Bedingung ) \end{eqnarray*}$ Kann dann auch der Fall auftreten, dass x=y ist? Vielen Dank für eure Hilfe.
13.11.2011, 14:03	chrizke	Auf diesen Beitrag antworten »
Klar, partielle Ordnungen sind doch antisymmetrisch.
13.11.2011, 14:13	stefan90	Auf diesen Beitrag antworten »
Das Problem ist, ich muss prüfen, ob eine Halbordnung vorliegt. Das ist die Relation: $\begin{eqnarray} Q \subseteq \Sigma^ \times \Sigma^, \forall x,y \in \Sigma^ : ( xQy :\Leftrightarrow \exists x' \in \Sigma^* : xx' = y) \end{eqnarray*}$
13.11.2011, 14:41	stefan90	Auf diesen Beitrag antworten »
Wenn $\begin{eqnarray} \Sigma^ = \left \{ 0, 1 \right \} \end{eqnarray}$ , dann gibt es doch folgende Relationen: (0,0e),(1,1e), (11, 11e)... -> Reflexiv, da jedes Element mit dem leeren Wort verknüpft zu sich selber in Relation steht. Antisymmetrie: Ja, weil stets gilt \|y\|>\|x\|. Nicht transitiv: Wenn gilt: (1, 01) und (01, 010), gilt nicht: (1, 010), denn ich kann ja 0 nichts anhängen, so dass ich 010 erhalte. Richtig? Damit ist es keine Halbordnung.
13.11.2011, 15:16	chrizke	Auf diesen Beitrag antworten »
Natürlich gilt die Transitivität: Es seien $\begin{eqnarray} x,y,z\in\Sigma^ \end{eqnarray}$ mit $\begin{eqnarray} xQy,\ yQz \end{eqnarray}$ dann existieren nach Definition doch $\begin{eqnarray} x',y'\in\Sigma^* \end{eqnarray}$ mit $\begin{eqnarray} xx'=y,\ \ yy'=z \end{eqnarray}$ und somit gilt ja offensichtlich $\begin{eqnarray} xx'y'=z\Rightarrow xQz \end{eqnarray}$ Zu deinem Beispiel, wenn $\begin{eqnarray} \Sigma^=\{0,1\} \end{eqnarray}$ . Dann sind 1 und 01 ein Wort über dem Alphabet. Allerdings gilt nicht $\begin{eqnarray} 1Q01 \end{eqnarray}$ , denn was willst du an die 1 rechts dranhängen, um links die 0 hinzubekommen?
13.11.2011, 15:27	stefan90	Auf diesen Beitrag antworten »
Ah, Zahlendreher. Kein Wunder komme ich zu einem falschen Schluss Also doch eine Halbordnung. Danke für deine Hilfe, chrizke
Anzeige

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »