Die Mathe-Redaktion - 17.09.2019 15:26 - Registrieren/Login
Auswahl
ListenpunktHome
ListenpunktAktuell und Interessant ai
ListenpunktArtikelübersicht/-suche
ListenpunktAlle Links / Mathe-Links
ListenpunktFach- & Sachbücher
ListenpunktMitglieder / Karte / Top 15
ListenpunktRegistrieren/Login
ListenpunktArbeitsgruppen
Listenpunkt? im neuen Schwätz
ListenpunktWerde Mathe-Millionär!
ListenpunktAnmeldung MPCT Sept.
ListenpunktFormeleditor fedgeo
Schwarzes Brett
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden. Mitglieder können den Matheplanet-Newsletter bestellen, der etwa alle 2 Monate erscheint.

Der Newsletter Okt. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 613 Gäste und 18 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
Matroids Matheplanet Forum Index
Moderiert von Bilbo
Theoretische Informatik » Formale Sprachen & Automaten » Was ist ein Shuffle?
Druckversion
Druckversion
Autor
Universität/Hochschule J Was ist ein Shuffle?
LernenWollen
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 06.06.2019
Mitteilungen: 46
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2019-07-22


Hallo!

In der Vorlesung und im Skript zum meinem Modul Theoretische Informatik 2 kommt ab und zu die Operation Shuffle vor. Bisher habe ich mich davor gedrückt, mich damit zu beschäftigen, da es nirgends definiert wurde.

Ich weiß schonmal, dass es ums Mischen geht. Aber wie genau sehen dann die Wörter eines Shuffles aus zwei semi-entscheidbaren Sprachen $A$ und $B$ aus?

Sagen wir, $A = \{\{a, b\}^*| $ Anzahl $ a = 2*$Anzahl $ b\}$
und $B = \{\{b, c\}^*| $ Anzahl $ b = 3*$Anzahl $ c\}$.

Wie sieht hierfür der Shuffle aus? In $A$ liegen Wörter wie $aab$ oder $aaaabb$, in $B$ liegt beispielsweise $bbbc$. Liegt im Shuffle aus $A$ und $B$ sowas wie $babbabc$ (Mischung aus $aab$ und $bbbc$)?
Wie wäre die resultierende Sprache definiert?
Und was ist das tragende Argument dafür, dass das Ergebnis ebenfalls semi-entscheidbar ist? Es macht Sinn, dass eine Mischung zweier von Turingmaschinen berechenbarer Sprachen ebenfalls von einer Turingmaschine berechnet werden kann.

Im Hinblick auf die Klausur möchte ich dennoch echte Klarheit erfahren und den Glauben daran, dass es geht mit dem Wissen ersetzen, wie es geht.

Vielen Dank für eure Antworten und Grüße
LernenWollen



  Profil  Quote  Link auf diesen Beitrag Link
Tetris
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 28.08.2006
Mitteilungen: 7577
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2019-07-22


Guen Abend!

Der Wikipedia-Artikel "Shuffle algebra" liefert eine Definition der Shuffle-Verknüpfung zweier Wörter und darauf aufbauend zweier Sprachen.

Lg, T.



  Profil  Quote  Link auf diesen Beitrag Link
LernenWollen
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 06.06.2019
Mitteilungen: 46
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2019-07-23


Danke für die Antwort!

Was bedeutet abxy + axby? Ist das ein Wort, sind das zwei Wörter?
Genauso 10aaaaa.
Ich verstehe das Kontrukt nicht. Wie es gebildet wird, kann ich ja noch nachvollziehen. Jedoch kann ich das Ergebnis nicht interpretieren.
Ich sehe nichtmal, ob das ein Wort ist. Immerhin ist das Plus-Symbol ja nicht automatisch Teil des Alphabets. Eine Konkatenation wirds auch nicht sein.

Danke für die Erklärung.

Grüße
LernenWollen



  Profil  Quote  Link auf diesen Beitrag Link
Tetris
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 28.08.2006
Mitteilungen: 7577
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2019-07-23


Das Shuffle-Produkt zweier Wörter ist als Summe von Wörtern definiert. So ist beispielsweise

ab ⧢ xy = abxy + axby + xaby + axyb + xayb + xyab

Die Rechenoperationen ⧢ und + besitzen damit bestimmte Eigenschaften (Rechenregeln). Die rechte Seite beschreibt aber weder ein neues Wort noch deren sechs, sondern eben eine abstrakte Summe von Wörtern. Es gelten Regeln, etwa

abxy + axby = axby + abxy

aber auch

aaaaa + aaaaa = 2aaaaa.

Lg, T.



  Profil  Quote  Link auf diesen Beitrag Link
LernenWollen
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 06.06.2019
Mitteilungen: 46
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, vom Themenstarter, eingetragen 2019-07-23


Also ergibt ein Shuffle von zwei Wörtern kein neues Wort.
Shuffle ist laut Skript über semi-entscheidbare Sprachen abgeschlossen (Beweis ist nicht enthalten).
Also sollte doch das Ergebnis erneut ein Wort sein oder zumindest eine semi-entscheidbare Sprache, nicht?

Was sagt das Ergebnis aus? Wofür kann eine solche abstrakte Summe Verwendung finden und wie kann das abgeschlossen sein?

Danke!

Grüße
LernenWollen



  Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6033
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, eingetragen 2019-07-23


"Riffle Shuffle" ist eine Mischtechnik für Karten.
Darauf basiert auch der Shuffle-Operator, der in dem In dem verlinkten Artikel erklärt wird. Alles andere zum Thema Shuffle-Produkt, Summe von Wörtern, ... ist für Dich nicht relevant.

Der Shuffle-Operator angewendet auf die Wörter ab und xyz ergibt die Menge
{abxyz, axbyz, axybz, axyzb, xabyz, xaybz, xayzb, xyabz, xyazb, xyzab}.
Der Shuffle-Operator angewandt auf zwei Sprachen A und B, ergibt die Sprache die genau die Wörter enthält, die sich aus einem Wort aus A und einem Wort aus B zusammenmischen lassen.
Sind A und B rekursiv-aufzählbar, so lassen sich auch alle Shuffle-Ergebnisse von Wörtern aus A und B rekursiv aufzählen. Man könnte bspw. mit der Diagonalisierungsmethode nacheinander alle Wortpaare (a,b) mit a aus A und b aus B aufzählen und dann für jedes Wortpaar nacheinander alle Shuffle-Ergebnisse erzeugen.

[Die Antwort wurde nach Beitrag No.2 begonnen.]



  Profil  Quote  Link auf diesen Beitrag Link
LernenWollen
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 06.06.2019
Mitteilungen: 46
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, vom Themenstarter, eingetragen 2019-08-22 20:54


Entschuldigung, dass ich so spät antworte.
Die Erklärung war sehr einleuchtend. Ich entnehme ihr auch, dass bazyx kein Ergebnis aus dem Shuffle von ab und xyz ist, da die Reihenfolge relevant scheint.
Wieso ist die Summe von Wörtern nicht relevant? Sind sie kein Teil der theoretischen Informatik oder warum sind sie nicht relevant?

Grüße
LernenWollen



  Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6033
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, eingetragen 2019-08-24 00:20


2019-08-22 20:54 - LernenWollen in Beitrag No. 6 schreibt:
Ich entnehme ihr auch, dass bazyx kein Ergebnis aus dem Shuffle von ab und xyz ist, da die Reihenfolge relevant scheint.
Richtig.


Wieso ist die Summe von Wörtern nicht relevant? Sind sie kein Teil der theoretischen Informatik oder warum sind sie nicht relevant?
Das ist natürlich ein Stückweit Spekulation, ich sitze ja nicht in Eurer Vorlesung. In dem Beispiel, das Du genannt hast, geht es nur um das "Mischen" von Wörtern. Nichts deutet darauf hin, dass es um eine Shuffle-Algebra(!) gehen könnte (von der ich hier zum ersten Mal gehört habe).
Vielleicht bist Du nur auf diese Wiki-Seite gestoßen, weil es zum Shuffle-Operator keine eigene Seite gibt(*).
Ich will nicht sagen, dass Shuffle-Algebren _nichts_ mit theoretischer Informatik zu tun haben, aber ich sehe keinen Bezug zu den von dir geschilderten Aufgaben.

(*) Man verkennt manchmal, dass viele Bezeichnungen in Vorlesungen eben nicht allgemein bekannt und weit verbreitet sind. Manchmal findet ein Prof' irgendeine Frage oder Anwendung interessant, spannend oder lehrreich (und verwendet sie in seiner Vorlesung), die man sonst in keinem Lehrbuch findet. Manchmal ist das auch volle Absicht, damit die Studenten nicht nur nach einer Musterlösung suchen, sondern selbst nachdenken...



  Profil  Quote  Link auf diesen Beitrag Link
LernenWollen
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 06.06.2019
Mitteilungen: 46
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, vom Themenstarter, eingetragen 2019-08-24 12:49


Ich danke für die Erläuterung sehr!

Freundliche Grüße
LernenWollen



  Profil  Quote  Link auf diesen Beitrag Link
LernenWollen hat die Antworten auf ihre/seine Frage gesehen.
LernenWollen hat selbst das Ok-Häkchen gesetzt.
LernenWollen wird per Mail über neue Antworten informiert.
Neues Thema [Neues Thema]  Druckversion [Druckversion]

 


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-2019 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. 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]