Matroids Matheplanet Forum Index
Moderiert von Bilbo
Theoretische Informatik » Formale Sprachen & Automaten » Was sind Wörter und Sprachen von Mengen (Mathematik für Informatiker)?
Autor
Universität/Hochschule Was sind Wörter und Sprachen von Mengen (Mathematik für Informatiker)?
djqwi2
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 12.01.2022
Mitteilungen: 28
  Themenstart: 2022-01-12 18:34

https://matheplanet.com/matheplanet/nuke/html/uploads/b/55293_oiki.png Hallo, was genau ist mit Sprache, Wörter, länge der Wörter diesem M*, diesem U hier gemeint? Das mit n-tupel kapier ich noch, dann hörts auf... GErade bei den gelb markierten.


   Profil
thureduehrsen
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 13.11.2007
Mitteilungen: 943
Wohnort: Kiel, Deutschland
  Beitrag No.1, eingetragen 2022-01-12 18:38

Hallo djqwi2, hier werden schlicht mehrere gebräuchliche Namen für denselben Sachverhalt genannt. In der theoretischen Informatik heißen n-Tupel, deren jede Komponente aus einem vorgegebenen Alphabet stammt, auch Wörter. Man orientiert sich hier zum Teil an aus der Grammatik oder allgemein Linguistik bekannten Begriffen, damit die Materie nicht gar zu trocken daherkommt. mfg thureduehrsen


   Profil
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 3197
  Beitrag No.2, eingetragen 2022-01-12 18:40

\(\begingroup\)\(\renewcommand{\Re}{\operatorname{Re}} \renewcommand{\Im}{\operatorname{Im}} \newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\d}{{\rm d}} \newcommand{\rg}{\operatorname{rg}} \newcommand{\spur}{\operatorname{spur}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\tr}{\operatorname{tr}} \newcommand{\opn}{\operatorname} \newcommand\ceil[1]{\left\lceil #1 \right\rceil} \newcommand\floor[1]{\left\lfloor #1 \right\rfloor}\) Hallo, damit ist genau das gemeint, was da steht, denn das ist eine Definition. In anderen Worten: "Wort der Länge $n$" ist ein Synonym für "$n$-Tupel". Das $\bigcup$ steht für die Vereinigungsmenge. Es ist also $M^* = M^0 \cup M^1 \cup M^2 \cup \ldots$. [Die Antwort wurde vor Beitrag No.1 begonnen.]\(\endgroup\)


   Profil
djqwi2
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 12.01.2022
Mitteilungen: 28
  Beitrag No.3, vom Themenstarter, eingetragen 2022-01-12 18:43

\quoteon(2022-01-12 18:38 - thureduehrsen in Beitrag No. 1) Hallo djqwi2, hier werden schlicht mehrere gebräuchliche Namen für denselben Sachverhalt genannt. In der theoretischen Informatik heißen n-Tupel, deren jede Komponente aus einem vorgegebenen Alphabet stammt, auch Wörter. Man orientiert sich hier zum Teil an aus der Grammatik oder allgemein Linguistik bekannten Begriffen, damit die Materie nicht gar zu trocken daherkommt. mfg thureduehrsen \quoteoff Danke also Sprache, ist dann das ganze karthesische Produkt und die Wörter die Tupel im Produkt? Und unten steht jedoch,d ass die Sprache eine Teilmenge von M* sei, was ist damit gemeitn?


   Profil
thureduehrsen
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 13.11.2007
Mitteilungen: 943
Wohnort: Kiel, Deutschland
  Beitrag No.4, eingetragen 2022-01-12 18:48

Hallo djqwi2, \quoteon(2022-01-12 18:43 - djqwi2 in Beitrag No. 3) Danke also Sprache, ist dann das ganze karthesische Produkt und die Wörter die Tupel im Produkt? Und unten steht jedoch,d ass die Sprache eine Teilmenge von M* sei, was ist damit gemeitn? \quoteoff Die betrachtete Sprache ist eine Teilmenge des gesamten kartesischen Produkts. Jedes Wort der Sprache ist ein Tupel. Ich tue mich schwer damit, deine Frage zu verstehen. Lasse dir mehr Zeit zum Überlegen und Verdauen der Antworten, die du hier erhältst. mfg thureduehrsen [Verschoben aus Forum 'Relationen und Abbildungen' in Forum 'Formale Sprachen & Automaten' von thureduehrsen]


   Profil
djqwi2
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 12.01.2022
Mitteilungen: 28
  Beitrag No.5, vom Themenstarter, eingetragen 2022-01-12 19:06

\quoteon(2022-01-12 18:48 - thureduehrsen in Beitrag No. 4) Hallo djqwi2, \quoteon(2022-01-12 18:43 - djqwi2 in Beitrag No. 3) Danke also Sprache, ist dann das ganze karthesische Produkt und die Wörter die Tupel im Produkt? Und unten steht jedoch,d ass die Sprache eine Teilmenge von M* sei, was ist damit gemeitn? \quoteoff Die betrachtete Sprache ist eine Teilmenge des gesamten kartesischen Produkts. Jedes Wort der Sprache ist ein Tupel. Ich tue mich schwer damit, deine Frage zu verstehen. Lasse dir mehr Zeit zum Überlegen und Verdauen der Antworten, die du hier erhältst. mfg thureduehrsen [Verschoben aus Forum 'Relationen und Abbildungen' in Forum 'Formale Sprachen & Automaten' von thureduehrsen] \quoteoff Okay danke, ich dachte aber eine Teilmenge des kartesischen produkts sei immer eine Relation o.O. Was genau ist dann eigentlich das Alphabet? Ist das die Menge?


   Profil
thureduehrsen
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 13.11.2007
Mitteilungen: 943
Wohnort: Kiel, Deutschland
  Beitrag No.6, eingetragen 2022-01-12 19:12

\quoteon(2022-01-12 19:06 - djqwi2 in Beitrag No. 5) Okay danke, ich dachte aber eine Teilmenge des kartesischen produkts sei immer eine Relation o.O. \quoteoff Das ist auch so. \quoteon Was genau ist dann eigentlich das Alphabet? Ist das die Menge? \quoteoff Das ist die Menge, der die Symbole oder Buchstaben angehören, aus denen die Wörter der Sprache bestehen. mfg thureduehrsen


   Profil
djqwi2
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 12.01.2022
Mitteilungen: 28
  Beitrag No.7, vom Themenstarter, eingetragen 2022-01-12 19:45

\quoteon(2022-01-12 19:12 - thureduehrsen in Beitrag No. 6) \quoteon(2022-01-12 19:06 - djqwi2 in Beitrag No. 5) Okay danke, ich dachte aber eine Teilmenge des kartesischen produkts sei immer eine Relation o.O. \quoteoff Das ist auch so. \quoteon Was genau ist dann eigentlich das Alphabet? Ist das die Menge? \quoteoff Das ist die Menge, der die Symbole oder Buchstaben angehören, aus denen die Wörter der Sprache bestehen. mfg thureduehrsen \quoteoff Aso, also ist dei Srpache=eine Relation und das Alphabet die Grundmenge?


   Profil
thureduehrsen
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 13.11.2007
Mitteilungen: 943
Wohnort: Kiel, Deutschland
  Beitrag No.8, eingetragen 2022-01-12 20:03

\(\begingroup\)\(\newcommand{\id}{\operatorname{id}}\) \quoteon(2022-01-12 19:45 - djqwi2 in Beitrag No. 7) Aso, also ist dei Srpache=eine Relation und das Alphabet die Grundmenge? \quoteoff Sei \(\Sigma\) ein Alphabet. Jede Sprache \(L\) über \(\Sigma\) ist eine Teilmenge von \(\Sigma^{\ast}\). Was \(\Sigma^\ast\) ist, steht im Themenstart. Hausaufgabe: Aufdröseln/erklären. Sei \(L\) eine Sprache über \(\Sigma\). Zu jedem \(w\in L\) gibt es ein \(n\in\mathbb{N}_0\) mit \(w\in\Sigma^n\). In diesem Fall heißt \(n\) die Länge von \(w\). Zu sagen, dass eine Sprache eine Relation ist, ist ungenau (strenggenommen falsch), denn unendlichstellige Relationen sind mir noch nicht begegnet, selbst in der englischsprachigen Wikipedia gibt es keinen Artikel dazu (wenngleich der Artikel zu Relationen den Titel Finitary relation trägt und die Existenz unendlichstelliger Relationen zumindest suggeriert). mfg thureduehrsen\(\endgroup\)


   Profil
tactac
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 15.10.2014
Mitteilungen: 2332
  Beitrag No.9, eingetragen 2022-01-12 23:50

Jede Teilmenge einer Menge "ist" (u.a.) eine einstellige Relation.


   Profil
thureduehrsen
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 13.11.2007
Mitteilungen: 943
Wohnort: Kiel, Deutschland
  Beitrag No.10, eingetragen 2022-01-13 05:32

\quoteon(2022-01-12 23:50 - tactac in Beitrag No. 9) Jede Teilmenge einer Menge "ist" (u.a.) eine einstellige Relation. \quoteoff Ja, schon, aber diese Sichtweise dürfte eher Verwirrung stiften... eine Relation soll doch mehrere Dinge in Beziehung setzen. mfg thureduehrsen


   Profil
tactac
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 15.10.2014
Mitteilungen: 2332
  Beitrag No.11, eingetragen 2022-01-13 09:42

\quoteon(2022-01-13 05:32 - thureduehrsen in Beitrag No. 10) \quoteon(2022-01-12 23:50 - tactac in Beitrag No. 9) Jede Teilmenge einer Menge "ist" (u.a.) eine einstellige Relation. \quoteoff Ja, schon, aber diese Sichtweise dürfte eher Verwirrung stiften... eine Relation soll doch mehrere Dinge in Beziehung setzen. \quoteoff Nein. 0- und 1-stellige Relationen gibt's nunmal. Und auch eine siebenstellige Relation kann u.U. überhaupt keine Dinge in Beziehung setzen. Verwirrung dürfte eher stiften, von unendlichstelligen Relationen zu sprechen. Wo soll hier eine solche sein?


   Profil
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 3080
  Beitrag No.12, eingetragen 2022-01-13 09:56

\quoteon(2022-01-13 09:42 - tactac in Beitrag No. 11) Verwirrung dürfte eher stiften, von unendlichstelligen Relationen zu sprechen. Wo soll hier eine solche sein? \quoteoff Eine Sprache ist eine unendlichstellige Relation (sprich: Teilmenge des kartesischen Produktes) über dem zugrundeliegenden Alphabet. Ich vermute mal, dass thureduehrsen etwas derartiges meint.


   Profil
tactac
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 15.10.2014
Mitteilungen: 2332
  Beitrag No.13, eingetragen 2022-01-13 11:05

\(\begingroup\)\(\newcommand{\sem}[1]{[\![#1]\!]} \newcommand{\name}[1]{\ulcorner#1\urcorner} \newcommand{\upamp}{\mathbin {⅋}}\) \quoteon(2022-01-13 09:56 - DerEinfaeltige in Beitrag No. 12) \quoteon(2022-01-13 09:42 - tactac in Beitrag No. 11) Verwirrung dürfte eher stiften, von unendlichstelligen Relationen zu sprechen. Wo soll hier eine solche sein? \quoteoff Eine Sprache ist eine unendlichstellige Relation (sprich: Teilmenge des kartesischen Produktes) über dem zugrundeliegenden Alphabet. Ich vermute mal, dass thureduehrsen etwas derartiges meint. \quoteoff Wie? $L \subseteq \Sigma^\IN$? Wie soll das gehen? Im Fall $\Sigma=\{1\}$ gibt es ja nur ein Element in $\Sigma^\IN$; $\Sigma^*$ dagegen ist gleichmächtig zu $\IN$.\(\endgroup\)


   Profil
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 3080
  Beitrag No.14, eingetragen 2022-01-13 11:41

Also ich würde unter einem unendlichen kartesischen Produkt über einer Menge $M$ intuitiv $M^*$ verstehen, also die Menge aller Tupel beliebiger Länge. Von daher existiert kein Widerspruch. Wenn der Begriff grundsätzlich etwas anderes meint - beispielsweise genau die Tupel unendlicher Länge - ergibt das natürlich keinen Sinn. Und wenn thureduehrsen etwas anderes meint als ich ihm dreist unterstellt habe, dann passt mein Beitrag natürlich auch nicht. Die Begriffe "Sprache" und "Relation" sind jedenfalls in soweit miteinander verwandt, dass es um die Frage geht, ob bestimmte Tupel/Zeichenketten Element der entsprechenden Menge sind. Ob diese Abstraktion und diese recht allgemeine Interpretation des Begriffs der Relation zielführend oder Verwirrung stiftend sind, ist eine andere Frage.


   Profil
Folgende Antworten hat der Fragesteller vermutlich noch nicht gesehen.
tactac
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 15.10.2014
Mitteilungen: 2332
  Beitrag No.15, eingetragen 2022-01-13 12:01

\(\begingroup\)\(\newcommand{\sem}[1]{[\![#1]\!]} \newcommand{\name}[1]{\ulcorner#1\urcorner} \newcommand{\upamp}{\mathbin {⅋}}\) Ok. Nun, $\Sigma^\IN$ ist ein kartesisches Produkt, $\Sigma^*$ ist kein kartesisches Produkt, außer vielleicht auf triviale Weise (mit einem "Faktor", nämlich $\Sigma^*$). Und dass einstellige Relationen einfach Teilmengen sind, erwähnte ich ja schon. $\Sigma^*$ kann man außerdem als Teilmenge von $(\Sigma+1)^\IN$ sehen ($\alpha \in \Sigma^* :\Leftrightarrow \exists n \in \IN.\, \forall i \in \IN.\, n \leq i \Leftrightarrow \alpha(i)=\mathrm{inr}(*)$), das ist aber auch wieder 'was sehr anderes als 'ne Teilmenge von $\Sigma^\IN$.\(\endgroup\)


   Profil
thureduehrsen
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 13.11.2007
Mitteilungen: 943
Wohnort: Kiel, Deutschland
  Beitrag No.16, eingetragen 2022-01-13 22:52

\(\begingroup\)\(\newcommand{\id}{\operatorname{id}}\) @DerEinfaeltige: Du hast mich vollständig richtig verstanden. \quoteon(2022-01-13 11:41 - DerEinfaeltige in Beitrag No. 14) Also ich würde unter einem unendlichen kartesischen Produkt über einer Menge $M$ intuitiv $M^*$ verstehen, also die Menge aller Tupel beliebiger Länge. \quoteoff Aber ich habe mich leider nicht so präzise ausgedrückt, wie ich es hätte tun müssen. @tactac: Was ist $\Sigma+1$? Was ist $\mathrm{inr}(*)$? Wie steht es nun mit dem Themenstarter? Haben wir ihn abgehängt? mfg thureduehrsen \(\endgroup\)


   Profil
tactac
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 15.10.2014
Mitteilungen: 2332
  Beitrag No.17, eingetragen 2022-01-13 23:55

\(\begingroup\)\(\newcommand{\sem}[1]{[\![#1]\!]} \newcommand{\name}[1]{\ulcorner#1\urcorner} \newcommand{\upamp}{\mathbin {⅋}}\) \quoteon(2022-01-13 22:52 - thureduehrsen in Beitrag No. 16) @DerEinfaeltige: Du hast mich vollständig richtig verstanden. \quoteon(2022-01-13 11:41 - DerEinfaeltige in Beitrag No. 14) Also ich würde unter einem unendlichen kartesischen Produkt über einer Menge $M$ intuitiv $M^*$ verstehen, also die Menge aller Tupel beliebiger Länge. \quoteoff Aber ich habe mich leider nicht so präzise ausgedrückt, wie ich es hätte tun müssen. \quoteoff Ja, also "unendliches kartesisches Produkt" kann man dazu ganz sicherlich nicht sagen. \quoteon @tactac: Was ist $\Sigma+1$? Was ist $\mathrm{inr}(*)$? \quoteoff $\Sigma+1$ ist das Koprodukt aus $\Sigma$ und $1$, $1$ "das" terminale Objekt, $\mathrm{inr}$ eine der zugehörigen Koprojektionen, $*$ das Element von $1$.\(\endgroup\)


   Profil
thureduehrsen
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 13.11.2007
Mitteilungen: 943
Wohnort: Kiel, Deutschland
  Beitrag No.18, eingetragen 2022-01-14 16:52

\(\begingroup\)\(\newcommand{\id}{\operatorname{id}}\) \quoteon(2022-01-13 23:55 - tactac in Beitrag No. 17) $\Sigma+1$ ist das Koprodukt aus $\Sigma$ und $1$, $1$ "das" terminale Objekt, $\mathrm{inr}$ eine der zugehörigen Koprojektionen, $*$ das Element von $1$. \quoteoff Das mag ja alles so stimmen, ist aber ziemlich weit von der theoretischen Informatik, dem Gebiet des Themenstart(er)s, entfernt... @djqwi2: kannst du deine Verständnisschwierigkeiten in Worte fassen? mfg thureduehrsen \(\endgroup\)


   Profil
tactac
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 15.10.2014
Mitteilungen: 2332
  Beitrag No.19, eingetragen 2022-01-14 21:50

\(\begingroup\)\(\newcommand{\sem}[1]{[\![#1]\!]} \newcommand{\name}[1]{\ulcorner#1\urcorner} \newcommand{\upamp}{\mathbin {⅋}}\) \quoteon(2022-01-14 16:52 - thureduehrsen in Beitrag No. 18) \quoteon(2022-01-13 23:55 - tactac in Beitrag No. 17) $\Sigma+1$ ist das Koprodukt aus $\Sigma$ und $1$, $1$ "das" terminale Objekt, $\mathrm{inr}$ eine der zugehörigen Koprojektionen, $*$ das Element von $1$. \quoteoff Das mag ja alles so stimmen, ist aber ziemlich weit von der theoretischen Informatik, dem Gebiet des Themenstart(er)s, entfernt... \quoteoff Nein. Kategorientheorie (plus damit zusammenhängende Notationen) ist ganz nah dran an theoretischer Informatik. Es ist ein nützliches Werkzeug, das mitunter auch als "Standardwerkzeug" gesehen wird. Siehe z.B. hier.\(\endgroup\)


   Profil
thureduehrsen
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 13.11.2007
Mitteilungen: 943
Wohnort: Kiel, Deutschland
  Beitrag No.20, eingetragen 2022-01-14 21:59

\quoteon(2022-01-14 21:50 - tactac in Beitrag No. 19) Nein. Kategorientheorie (plus damit zusammenhängende Notationen) ist ganz nah dran an theoretischer Informatik. Es ist ein nützliches Werkzeug, das mitunter auch als "Standardwerkzeug" gesehen wird. Siehe z.B. hier. \quoteoff Du bist Senior, und ich bin Senior. Der TS ist es nicht. mfg thureduehrsen


   Profil
tactac
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 15.10.2014
Mitteilungen: 2332
  Beitrag No.21, eingetragen 2022-01-14 22:15

\quoteon(2022-01-14 21:59 - thureduehrsen in Beitrag No. 20) \quoteon(2022-01-14 21:50 - tactac in Beitrag No. 19) Nein. Kategorientheorie (plus damit zusammenhängende Notationen) ist ganz nah dran an theoretischer Informatik. Es ist ein nützliches Werkzeug, das mitunter auch als "Standardwerkzeug" gesehen wird. Siehe z.B. hier. \quoteoff Du bist Senior, und ich bin Senior. Der TS ist es nicht. \quoteoff Kein Grund, falsche Aussagen unkorrigiert stehenzulassen oder darauf zu verzichten, halbwegs ähnliche wahre Aussagen zum Vergleich anzugeben.


   Profil

Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2022 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]