Gibt es eine bekannte Methode zum Erstellen einer Grammatik bei einer endlichen Menge endlicher Zeichenfolgen?

10

Aus meiner Lektüre geht hervor, dass es bei den meisten Grammatiken darum geht, eine unendliche Anzahl von Zeichenfolgen zu erzeugen. Was ist, wenn Sie umgekehrt gearbeitet haben?

Wenn n Zeichenfolgen mit einer Länge von m angegeben werden, sollte es möglich sein, eine Grammatik zu erstellen, die diese Zeichenfolgen und nur diese Zeichenfolgen generiert.

Gibt es dafür eine bekannte Methode? Idealerweise ein Technikname, den ich erforschen kann. Wie würde ich alternativ eine Literatursuche durchführen, um eine solche Methode zu finden?

formal-languages regular-languages formal-grammars finite-sets Gustav Bertram
quelle

5

Trivial: Erstellen Sie eine BNF-Tabelle der Zeichenfolgen.

Joshua

Strings sind per Definition endlich. Und Sie können nicht eine unendliche Menge "gegeben" bekommen, wenn Sie nicht eine endliche Beschreibung davon haben.

vonbrand

11

Dies fällt unter das allgemeine Thema "Grammatikinduktion"; Wenn Sie nach diesem Satz suchen, werden Sie eine Menge Literatur finden. Siehe z. B. Induzieren einer kontextfreien Grammatik , https://en.wikipedia.org/wiki/Grammar_induction , /cstheory//q/27347/5038 .

Für reguläre Sprachen (anstatt kontextfreie) siehe auch Ist Regex Golf NP-Complete? , Kleinste DFA , die Strings gegeben annimmt und verwirft andere gegebenen Strings , Gibt es Verbesserungen auf Dana Angluin Algorithmus für reguläre Sätze zu lernen , und /cstheory//q/1854/5038 .

DW
quelle

Das Induzieren von Grammatiken für möglicherweise unendliche reguläre Sprachen ist schwierig und unterscheidet sich erheblich von diesem Problem.

Reinierpost

Ich markiere diese Frage als richtig, denn obwohl sie die Frage nicht direkt beantwortet (was sich wie angegeben als trivial lösbar herausstellt), liefert sie mir die Art von Terminologie, die ich für weitere Untersuchungen benötige.

Gustav Bertram

8

$S=\{s_1,s_2....s_m\}$ $A$ $A \to s_1|s_2|...s_n$

Sashas
quelle

Ich denke, ich muss mein Parsing-Lehrbuch überprüfen. Rückblickend scheint diese Antwort offensichtlich. Danke!

Gustav Bertram

3

Es gibt viele Möglichkeiten, daher müssen Sie der Qualität der Ergebnisse zusätzliche Kriterien auferlegen.

$w$ $S \rightarrow w$ $S$
$w$ $X_w$ $w_1xw_2$ $x$ $X_{w_1} \rightarrow xX_{w_2}$ $w$ $X_w \rightarrow \epsilon$ $X_\epsilon$
Suffixbaum: das gleiche, umgekehrt.
Anwenden eines Algorithmus, der garantiert eine Grammatik von minimaler Größe erzeugt, z. B. mit der minimalen Anzahl von Regeln. Ich weiß nicht, wie schwer das ist.

Reinierpost
quelle

Ja, nach der ersten Antwort war es offensichtlich, dass ich zusätzliche Kriterien hätte auferlegen sollen, aber es fühlte sich unfair an, die Frage nach der ersten Antwort zu ändern.

Gustav Bertram

Trotzdem würde ich gerne wissen, wie zeitlich komplex es ist, eine minimale Grammatik für einen bestimmten endlichen Satz von Zeichenfolgen zu finden ... sagen wir, in der Gesamtlänge der Zeichenfolgen oder in der Gesamtlänge des Ergebnisses.

Reinierpost

3

Was Sie fragen, ähnelt einem Suchindex. In der Tat können Finite-State-Wandler erstellt und verwendet werden, um ihnen zugeführten Text zu erkennen. Zum Beispiel verwendet Lucene diesen Algorithmus: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.24.3698

Für eine praktische Anwendung lesen Sie diesen Blog-Beitrag von Andrew Gallant: Index 1.600.000.000 Schlüssel mit Automaten und Rost

In dem Beitrag beschreibt er eine Methode, um eine FSA mit einem Textkorpus so zu konstruieren, dass alle Wörter erkannt werden. Das Endergebnis ist die Erstellung einer ungefähr minimalen FST aus vorsortierten Schlüsseln in linearer Zeit und in konstantem Speicher.

Die Implementierung ist in seiner fstBibliothek verfügbar : https://github.com/BurntSushi/fst

lkraider
quelle

1

Eine Antwort auf die Frage von reinierpost, die auch die ursprüngliche Frage beantwortet:

Wir konstruieren den Wörterbuchautomaten wie folgt:

Konstruieren Sie einen Automaten, der genau die erste Zeichenfolge liest und akzeptiert.
Beginnen Sie für die nächste Zeichenfolge mit dem Lesen des Automaten, bis für einen Buchstaben kein Übergang mehr erfolgt. Starten Sie einen neuen Zweig für den Rest der Zeichenfolge. Wiederholen, bis alle Zeichenfolgen verarbeitet sind

Die maximale Größe des Automaten ist die Gesamtlänge der Eingabezeichenfolgen. Angenommen, Sie können Übergänge simulieren und in konstanter Zeit neue erstellen, dann ist auch die Laufzeit die Gesamtlänge der Eingabezeichenfolgen. Keine besten oder schlechtesten Fälle.

Dieser Automat ist minimal. Da im regulären Fall Automaten und Grammatiken fast eins zu eins entsprechen, gilt dies auch für die Grammatik. Natürlich ist es unmöglich, etwas der Größe n in weniger als n Zeit zu konstruieren.

Peter Leupold
quelle

Vielen Dank. Zur Beantwortung dieser Frage: Ich sehe nicht, was dies über Reinierpost beiträgt. Wir möchten auch keine Antworten, die auf eine andere Antwort antworten oder diese kommentieren: Dies ist kein Diskussionsforum. Der Weg, dies zu tun, wäre, eine neue Frage zu posten und sie dann selbst zu beantworten. Mir ist klar, dass das vielleicht nicht offensichtlich ist. [Das heißt, ich sehe nicht, wie Ihre Antwort das Problem beantwortet, auf das Reinierpost neugierig war. Das Problem am Ende der Antwort von reinierpost bestand darin, eine Grammatik mit der Mindestanzahl von Regeln zu finden. Ihre Antwort zeigt, wie Sie einen DFA mit einer minimalen Anzahl von Status erstellen. (Fortsetzung)

DW

1

Natürlich können wir diesen DFA in eine reguläre Grammatik umwandeln, aber warum glauben Sie, dass er in Bezug auf die Anzahl der Regeln in der Grammatik minimal sein wird? Es scheint, dass das Beweise braucht.]

DW

Was meine Antwort beiträgt, ist die Laufzeit, denke ich. Sie haben Recht, einige Dinge, die ich sage, brauchen einen Beweis. Die Entsprechung zwischen Übergängen endlicher Automaten und Regeln der regulären Grammatik ist für mich jedoch sehr klar (wenn letztere wie in den meisten Definitionen nur ein Terminal pro Regel generieren können). dann würde jede Grammatik, die kleiner als meine ist, einen Automaten ergeben, der kleiner als der minimale ist. Ich denke also, dass die Grammatik des Minimalautomaten (ich beweise nicht, dass meine minimal ist) auch minimal sein wird. - Ich werde Ihren Rat bezüglich der Antworten im Auge behalten, danke

Peter Leupold

Der Begriff der Minimalität für DFAs bezieht sich auf die Anzahl der Staaten . Bedeutet dies eine Minimalität in Bezug auf die Anzahl der Übergänge im DFA oder eine Minimalität der Anzahl der Regeln in der resultierenden Grammatik? Ich denke, wir müssen nachverfolgen, was Ihre Metrik ist, da ich sonst befürchte, wir werden Äpfel mit Orangen vergleichen.

DW

Richtig, die Grammatik ist in Termson-Nicht-Terminals minimal. Für Regeln ist dies nicht klar.

Peter Leupold

Gibt es eine bekannte Methode zum Erstellen einer Grammatik bei einer endlichen Menge endlicher Zeichenfolgen?

Antworten: