Definition eines Worts < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 12:26 Sa 26.03.2011 | | Autor: | bandchef |
| Aufgabe | | Ich will die Definition Wort klären. |
Ich hab hier folgende Definition:
Sei [mm] $\Sigma$ [/mm] ein Alphabet. Ein Wort über [mm] $\Sigma$ [/mm] ist eine endliche (eventuell leere) Folge von Buchstaben aus [mm] $\Sigma$. [/mm] Das leere Wort [mm] $\epsilon$ [/mm] ist die leere Buchstabenfolge. Die Menge aller Wörter über [mm] $\Sigma$ [/mm] bezeichnen wir mit [mm] $\Sigma^{\ast}$. [/mm] Ferner sei [mm] $\Sigma^+ [/mm] = [mm] \Sigma^{\ast} [/mm] - [mm] \{\epsilon}$ [/mm] die Menge aller Wörter über [mm] $\Sigma$ [/mm] - ausgenommen dem leeren Wort.
Mir ist irgendwie nicht klar, was [mm] $\Sigma^{\ast}$ [/mm] ist.
Das [mm] $\Sigma$ [/mm] ist ja ein Alphabet nehmen wir z.B. alle kleine lateinischen Buchstaben und somit ist das eine endliche Folge, da ja das Alphabet begrenzt ist. Heißt das nun, dass [mm] $\Sigma^{\ast}$ [/mm] ebenfalls eine endliche Menge ist, die aus allen möglichen Kombinationen aus [mm] $\Sigma$ [/mm] besteht?
Wenn das nun richtig ist, dann wär mir [mm] $\Sigma^+ [/mm] = [mm] \Sigma^{\ast} [/mm] - [mm] \{\epsilon}$ [/mm] auch klar, denn das heißt ja dann, dass [mm] $\Sigma^+$ [/mm] aus allen Kombinationen von [mm] $\Sigma$ [/mm] besteht, nur eben ist das leere Wort [mm] $\epsilon$ [/mm] nicht mitdabei.
Könnt ihr mir helfen?
|
|
| |
|
Hallo,
> Ich will die Definition Wort klären.
>
> Ich hab hier folgende Definition:
>
> Sei [mm]\Sigma[/mm] ein Alphabet. Ein Wort über [mm]\Sigma[/mm] ist eine
> endliche (eventuell leere) Folge von Buchstaben aus [mm]\Sigma[/mm].
> Das leere Wort [mm]\epsilon[/mm] ist die leere Buchstabenfolge. Die
> Menge aller Wörter über [mm]\Sigma[/mm] bezeichnen wir mit
> [mm]\Sigma^{\ast}[/mm]. Ferner sei [mm]\Sigma^+ = \Sigma^{\ast} - \{\epsilon\}[/mm]
> die Menge aller Wörter über [mm]\Sigma[/mm] - ausgenommen dem
> leeren Wort.
>
> Mir ist irgendwie nicht klar, was [mm]\Sigma^{\ast}[/mm] ist.
>
> Das [mm]\Sigma[/mm] ist ja ein Alphabet nehmen wir z.B. alle kleine
> lateinischen Buchstaben und somit ist das eine endliche
> Folge, da ja das Alphabet begrenzt ist. ![[ok]](/images/smileys/ok.gif "[ok]") Heißt das nun,
> dass [mm]\Sigma^{\ast}[/mm] ebenfalls eine endliche Menge ist,
Nein, wieso?
In [mm]\Sigma^{\ast}[/mm] sind doch alle möglichen Wörter - auch unsinnige - aller möglichen (unterschiedlichen) Längen, die du aus den Zeichen des Alphabetes [mm]\Sigma[/mm] kombinieren kannst.
Schon über dem Alphabet [mm]\Sigma=\{a,b\}[/mm] hast du doch [mm]\Sigma^{\ast}=\{\epsilon,a,b,ab,aa,ba,bb,aaa,aab,aba,baa,abb,bba,bab,bbb,.....\}[/mm]
> die aus allen möglichen Kombinationen aus [mm]\Sigma[/mm] besteht?
Ja, und die Wörter haben bel. endliche Länge ...
>
> Wenn das nun richtig ist, dann wär mir [mm]\Sigma^+ = \Sigma^{\ast} - \{\epsilon\}[/mm]
> auch klar, denn das heißt ja dann, dass [mm]\Sigma^+[/mm] aus allen
> Kombinationen von [mm]\Sigma[/mm] besteht, nur eben ist das leere
> Wort [mm]\epsilon[/mm] nicht mitdabei.
Hmm, ja, ich glaube, du meinst es richtig.
In [mm]\Sigma^+[/mm] sind alle möglichen Wörter endlicher Länge, die aus den Zeichen des Alphabetes [mm]\Sigma[/mm] zusammengesetzt werden können außer dem leeren Wort.
[mm]\Sigma^+[/mm] ist wie auch [mm] $\Sigma^{\ast}$ [/mm] nicht endlich!
>
> Könnt ihr mir helfen?
Gruß
schachuzipus
|
|
|
|
