Ok, ihr habe es ja so gewollt
heisenberg hat geschrieben: 
08.01.2021 13:02:33
Das läuft gerade schon so, wie ich das gut haben kann: Ich habe eine Idee und sie wird entweder widerlegt oder nicht. Und das Spielchen geht so lange weiter, bis einer keine Lust mehr hat, oder die Erkenntnis steht: Ja, das geht definitiv (nicht)!
Wenn ein theoretischer Informatiker da wäre, ist die Frage ob ich den überhaupt verstehen würde!
Ich versuchs mal so zu erklären dass man das auch ohne Studium verstehen kann. Sag Bescheid, falls was unverständlich ist. Und falls ich was durcheinandergeworfen hab, das Thema ist bei mir auch schon nen paar Tage her, wer es frischer gelernt hat, mag Fehler daher gerne korrigieren.
Der Begriff "Sprache" bezeichnet eine Menge von Elementen, die (in bestimmter Anordnung und Wiederholung als sogenannte "Wörter") strukturell zusammengefasst werden können. Die Sprache "a" z.B. könnte gebildet werden aus einer beliebigen Anzahl von "a", jedoch mindestens ein "a" und bis zur maximalen Länge von 5 "a", somit wären die Sprache "a" gebildet aus der Menge der folgende Wörter: "a", "aa", "aaa", "aaaa", "aaaaa". "ab" wäre hier aber kein Wort der Sprache.
Die Bildungsvorschriften können komplexer sein, so gibt es auch die Besonderheit namens ɛ (Epsilon, dem "leeren Wort", also ein Wort das kein "Zeichen" enthält. Ähnlich wie NULL, nicht 0, nicht nichts aber auch nichts... wollte hier nicht jemand mehr Philosophie im Forum?
) ... Du hast nun also nen Berg "Sprachen", die will man aber auch irgendwie ordnen, nach bestimmten Eigenschaften. Da hat sich ein Herr namens Chomsky mal drangesetzt. Der sagte, es gibt ne Menge von Klassen und jede dieser Klassen hat ne weitere bestimmte besondere Eigenschaft, die die Klasse davor nicht hatte. Er nennt die Sachen Typ-3, Typ-2 usw., nicht von den Zahlen verwirren lassen, eigentlich kommt's nur darauf an,
https://upload.wikimedia.org/wikipedia/ ... ie.svg.png dass bestimmte "Sprachen" strukturelle Eigenschaften haben, die andere so nicht haben.
Nun muss man ein paar Grundannahmen treffen. Dass die zutreffend sind, zeigt man im ersten bzw zweiten Semester, ich erspare Dir das hier, falls Du zweifelst oder Literaturempfehlungen haben willst, kann ich nen paar ISBN nachreichen, Schönings "Theoretische Informatik" sollte das ganze Thema ausreichend weit behandeln, wenn ich das noch richtig im Kopf hab.
Es gibt eine spezielle Struktur (die von regulären Sprachen), die hat die besondere Eigenschaft, dass man sie als eine sehr spezielle Art von Graph darstellen kann, einem DFA. Das ist auch wieder ein sehr lustiges Konstrukt der Theoretiker: Ein DFA ist wie ein kleines Monster, es frisst Zeichen und bewegt sich dabei. Wenn das Monster alles aufgefressen hat, und sich am Ende irgendwo befindet wo es ihm gefällt, sagt es "ja, das war ein gutes Wort, das gehört zur Sprache" (nennt sich dann "akzeptierender Endzustand"). Bekommt es was zu fressen, mit dem es nichts anfangen kann, sagt es "igitt, das will ich nicht, das gehört nicht auf meinen Speiseplan" (in theoreitschinformatisch: "das Wort ist nicht Teil der Sprache").
Man kann nen DFA auch mit nem U-Bahnplan vergleichen: Jedesmal wenn Du ein Zeichen gelesen hast, muss die Bahn eine Station weiterfahren, aber nur wenn das Zeichen eine Verbindung zur nächsten Station symbolisiert. Sind die Zeichen alle, steigst Du aus. Bist Du nun da, wo du sein wolltest, waren deine Zeichen ein Wort der Sprache, bist Du woanders, oder konnte der Zug nicht mit nem "a" vom Rathaus zum Markt fahren, war das, was Du der Bahn geboten hast, halt kein Wort der Sprache.
Jetzt gibt es noch ein zweites Konstrukt, den NFA, der ist praktisch das selbe in grün, nur dass man mehrere Stationen zu einer Schnellstrecke zusammenfassen kann. Und als nächstes muss man wissen, NFA und DFA sind zwar unterschiedliche Dinge, es gibt aber nen Beweis, der sagt, dass man durch regelkonformes Einfügen bzw Weglassen, den einen in den anderen verwandeln kann. Aus gutem Grund bevorzugt man in Computerprogrammen NFA, da man dann nicht so (unendlich) viel Speicherplatz braucht. Das A in DFA und NFA steht für finiter Automat. D wie deterministisch.
Nun gilt: gibt es einen DFA, dann gibt es dazu auch ne reguläre Sprache und diese reguläre Sprache ist durch die dazupassende reguläre Grammatik (den Bildungsregeln, wie "endlich viele a, mindestens 1 aber maximal 5") beschrieben (bzw "erzeugt").
Und nun kommt der für die eher praktisch veranlagten interessante Teil: immer dann, wenn das vorgesagte gilt, dann gibt es auch einen "Regulären Ausdruck" gibt, mit dem der Automat beschreiben werden kann (genauer, die Wege, die die U-Bahn nehmen darf, um alle Wörter der Sprache abzubilden).
Wichtig ist, dass der einfache finite Automat kein Gedächnis hat. Er weis nicht, was noch kommt, noch kann er sich daran erinnern, was und wieviel er bereits gefuttert hat, er hat auch keine Ahnung wie er dahin gekommen ist, wo er nun ist. Alles was er sagen kann ist: "gefällt mir hier", "gefällt mir hier nicht".
Soweit noch mitbekommen? War vielleicht etwas viel Unbekanntes auf einmal, aber die Grundlagen braucht man fürs Verständnis des Problems. Das war jetzt gut ein halbes Semester im Schnelldurchflug, ich entschuldige mich ausdrücklich für den verzettelten Blödsinn, das ist wirklich nur als unglaublich grober Überblick gemeint und erhebt keinerlei Anspruch auf Korrektheit. Die Wikipediaartikel zu den genannten Stichworten führen das genauer und teilweise auch sehr viel besser aus, manchmal steht man da aber ohne mathematisch/theoretisches/linguistisches Vorwissen aber im strömenden Regen.
Will man, dass der Automat mitzählen kann, bzw ein (kleines) Gedächnis hat, braucht es Kellerautomaten, Stackmaschines. Damit sind wir dann aber eine Klasse weiter.
Wenn Deine Sprache aber schon durch einen einfachen DFA abbildbar ist, dann (und zwar nur genau dann) darf man sie eine Reguläre Sprache nennen. Und dann gibt es auch (mindestens) einen regulären Ausdruck, mit dessen Hilfe man entscheiden kann, ob ein Wort zu dieser Sprache gehört oder nicht.
Und nun zu dem eigentlich Problem: Kann ich zeigen, dass man eindeutig sagen kann "ich bin vom Anfang zum Ende in endlich vielen Schritten durch meinen DFA gelaufen und dort geendet, wo es mir gefällt"? Oder gibt es die Möglichkeit, dass ich zwischendurch nicht mehr eindeutig sagen kann, gefällt es mir hier oder nicht - und wie geht's von hier weiter. In einigen Fällen ist es einfach zu erkennen, ob das Wort zur Sprache gehört, in anderen schwierig.
Und die Praxis macht's dann noch schwerer, weil einige Implementationen von "regulären" Ausdrücken, entgegen der formalen Anforderung, doch ein oft wenig mitzählen oder den Blick in Vergangenheit und Zukunft erlauben, was nach der reinen Lehre dort nichts zu suchen hätte. Die Stichworte dazu sind Backreferenz und Lookahead.
Wenn man zurück zu den Klassen geht, Typ-3 hatten wir anfangs, als nächstes kämen dann die kontextfreien Sprachen/Grammatiken und dann die kontextsensitiven. An der Stelle darf man sich dann mit dem Dangeling-Else-Problem rumschlagen, bevor wir ganz allgemein bei strukturierten Sprachen landen. Dann gehts über zu den natürlichen Sprachen. Und dann gehts zu der Frage nach der Semantik in der Sprache. Weitergehende Begriffe für die Suchmaschine wäre erstmal die Chomsky Hierarchie und dann, für die formalen Beweise wichtig, das gute alte Pumping Lemma, das Horden von Zweitsemestern an den Rand ihrer geistigen Gesundheit getrieben hat. Viel Spass auf der Reise
