Ich bin auf der Suche nach der mathematischen Theorie, die sich mit der Beschreibung von formalen Sprachen (Menge von Strings) im Allgemeinen und nicht nur mit Grammatikhierarchien beschäftigt.Gibt es eine andere Möglichkeit, eine andere formale Sprache als Grammatiken zu beschreiben?
Grammatiken geben Ihnen den Algorithmus, der alle möglichen Zeichenfolgen in der Sprache auflistet. Sie können den Algorithmus auf andere Weise spezifizieren, aber Grammatiken sind ein prägnantes und gut akzeptiertes Format dafür.
Eine andere Möglichkeit besteht darin, jede Zeichenkette aufzulisten, die zur Sprache gehört - dies funktioniert nur, wenn die Zeichenkette in der Sprache klein ist (und definitiv nicht, wenn die Menge unendlich ist).
Ich weiß aber, welche anderen "prägnanten und gut akzeptierten" Formate gibt es, um Sprachen zu beschreiben? – mtanti
Schreiben Sie beispielsweise ein Computerprogramm. Sie müssen das Programm nicht ausführen - der Code selbst ist eine Codierung der Sprache (der Menge der zur Sprache gehörenden Zeichenfolgen). Wenn Sie das Programm ausführen, generieren Sie tatsächlich die Zeichenfolgen in der Sprache, genau wie beim "Ausführen" der Grammatik (Anwenden der Regeln). – Attila
Reguläre Ausdrücke sind zum Beispiel ein Formalismus zum Beschreiben einer Reihe von Sprachen. Obwohl es Algorithmen gibt, um reguläre Grammatiken und Ausdrücke auf beide Arten zu transformieren, sind sie immer noch zwei verschiedene Theorien. Auch können Automaten (als ein Plural von Automaten) Ihnen helfen, Sprachen zu beschreiben, nicht nur DFA und NFA, die die gleiche Menge wie reguläre Sprachen beschreiben, sondern 2DFA, Stapelautomaten. Zum Beispiel ist ein Zwei-Stack-Automat so leistungsfähig wie eine Turing-Maschine. Schließlich sind Turing-Maschinen selbst ein Formalismus für Sprachen. Für jede Turing-Maschine ist die Menge aller Strings, auf denen die gegebene Turing-Maschine in einer endlichen Anzahl von Schritten stoppt, eine formal definierte Sprache.
Wissen Sie, ob es Algorithmen gibt, die Automaten aus String-Beispielen induzieren? – mtanti
Sie wissen, ich habe seit einiger Zeit darüber nachgedacht. Wir haben hier in meiner Fakultät experimentiert, indem Sie reguläre Ausdrücke an Samples angepasst haben, genau wie das Anpassen einer Funktion an einige Daten. Wir haben eine Idee, als würden wir eine Metaheuristik verwenden, um den minimalen Fehler zwischen einem regulären Ausdruck und einer Menge von Samples zu finden. Aber ich weiß nicht, was da draußen ist. –
Tatsächlich gibt es einen ganzen Zweig namens "grammatische Inferenz", der genau dieses Problem behandelt. Sie können wahrscheinlich dort starten. Überprüfen Sie Wikipedia. –
Ich schlage vor, Sie stellen Ihre Frage in http://cstheory.stackexchange.com statt –
Das wäre eine gute Idee, aber warum gibt es relevante Tags für dieses Thema auf Stackoverflow? – mtanti
Weil nicht jede Frage, die diese Konzepte beinhaltet, hier nicht zum Thema gehört und besser zu einer anderen Seite passt. –