Produzieren eines Satzes aus einer Grammatik mit einer bestimmten Anzahl von Endgeräten

Question

Sagen Sie bitte ein Spielzeug Grammatik haben, wie: (aktualisiert, so dass der Ausgang natürlicher aussieht)

S -> ${NP} ${VP} | ${S} and ${S} | ${S}, after which ${S}

NP -> the ${N} | the ${A} ${N} | the ${A} ${A} ${N}

VP -> ${V} ${NP}

N -> dog | fish | bird | wizard

V -> kicks | meets | marries

A -> red | striped | spotted

z. B. „der Hund schlägt den roten Zauberer“, „der Vogel trifft der gefleckte Fisch oder der Assistent heiratet den gestreiften Hund“

Wie kann man einen Satz aus dieser Grammatik nach der Einschränkung erzeugen, die es insgesamt n Vs + As + Ns enthält. Gegeben muss eine ganze Zahl der Satz, dass viele Terminals enthalten. (Anmerkung natürlich in dieser Grammatik der minimal mögliche n 3).

Answer 1

Der folgende Python-Code wird einen zufälligen Satz mit der angegebenen Anzahl von Endgeräten erzeugen. Es funktioniert, indem die Anzahl der Möglichkeiten zu zählen, einen Satz von einer bestimmten Länge und erzeugt eine große Zufallszahl und Berechnung des angegebenen Satz zu erzeugen. Die Zählung wird rekursiv durchgeführt, mit memoization. Eine leere rechte Seite erzeugt 1 Satz, wenn n 0 und 0 Sätze anders. Um die Anzahl der Sätze, die von einer nicht leeren rechten Seite erzeugten Anzahl, Summe über i, die Anzahl der Anschlüsse durch das erste Symbol in der rechten Seite verwendet. Für jeden i, die Anzahl der Möglichkeiten für den Rest der rechten Seite durch die Anzahl der Möglichkeiten für das erste Symbol multipliziert. Wenn das erste Symbol ein Terminal ist, gibt es 1 Möglichkeit, wenn i 1 ist und 0 sonst. Wenn das erste Symbol ein Nicht-End ist, fasst die Möglichkeiten über jede Alternative. Um Endlosschleifen zu vermeiden, müssen wir vorsichtig sein, um die rekursive Aufrufe zu beschneiden, wenn eine Menge 0 ist. Dies kann unendlich noch Schleife, wenn die Grammatik unendlich viele Ableitungen eines Satzes hat. Zum Beispiel in der Grammatik

S -> S S
S ->

gibt es unendlich viele Ableitungen des leeren Satzes: S =>, S => S S =>, S => S S => S S S => usw. Der Code einen bestimmten Satz zu finden, ist eine einfache Modifikation des Codes, sie zu zählen. Dieser Code ist einigermaßen effizient und erzeugt 100 Sätze mit 100 Anschlüssen jeweils in weniger als eine Sekunde.

import collections
import random

class Grammar:
    def __init__(self):
        self.prods = collections.defaultdict(list)
        self.numsent = {}
        self.weight = {}

    def prod(self, lhs, *rhs):
        self.prods[lhs].append(rhs)
        self.numsent.clear()

    def countsent(self, rhs, n):
        if n < 0:
            return 0
        elif not rhs:
            return 1 if n == 0 else 0
        args = (rhs, n)
        if args not in self.numsent:
            sym = rhs[0]
            rest = rhs[1:]
            total = 0
            if sym in self.prods:
                for i in xrange(1, n + 1):
                    numrest = self.countsent(rest, n - i)
                    if numrest > 0:
                        for rhs1 in self.prods[sym]:
                            total += self.countsent(rhs1, i) * numrest
            else:
                total += self.countsent(rest, n - self.weight.get(sym, 1))
            self.numsent[args] = total
        return self.numsent[args]

    def getsent(self, rhs, n, j):
        assert 0 <= j < self.countsent(rhs, n)
        if not rhs:
            return ()
        sym = rhs[0]
        rest = rhs[1:]
        if sym in self.prods:
            for i in xrange(1, n + 1):
                numrest = self.countsent(rest, n - i)
                if numrest > 0:
                    for rhs1 in self.prods[sym]:
                        dj = self.countsent(rhs1, i) * numrest
                        if dj > j:
                            j1, j2 = divmod(j, numrest)
                            return self.getsent(rhs1, i, j1) + self.getsent(rest, n - i, j2)
                        j -= dj
            assert False
        else:
            return (sym,) + self.getsent(rest, n - self.weight.get(sym, 1), j)

    def randsent(self, sym, n):
        return self.getsent((sym,), n, random.randrange(self.countsent((sym,), n)))

if __name__ == '__main__':
    g = Grammar()
    g.prod('S', 'NP', 'VP')
    g.prod('S', 'S', 'and', 'S')
    g.prod('S', 'S', 'after', 'which', 'S')
    g.prod('NP', 'the', 'N')
    g.prod('NP', 'the', 'A', 'N')
    g.prod('NP', 'the', 'A', 'A', 'N')
    g.prod('VP', 'V', 'NP')
    g.prod('N', 'dog')
    g.prod('N', 'fish')
    g.prod('N', 'bird')
    g.prod('N', 'wizard')
    g.prod('V', 'kicks')
    g.prod('V', 'meets')
    g.prod('V', 'marries')
    g.prod('A', 'red')
    g.prod('A', 'striped')
    g.prod('A', 'spotted')
    g.weight.update({'and': 0, 'after': 0, 'which': 0, 'the': 0})
    for i in xrange(100):
        print ' '.join(g.randsent('S', 3))

Answer 2

Vielleicht nicht die beste Lösung, aber ich würde meine Art und Weise rekursiv arbeiten durch jede Regel der Grammatik, bis ich die Beschränkung überschritten haben, dann Pop zurück und einen anderen Weg entlang der Grammatik erkunden. Halten Sie alle Sätze, die die Einschränkung und werfen alle Sätze treffen, die dies nicht tun.

Zum Beispiel mit n = 3:

S -> ($ {NP} $ {VP}) -> ((die $ {N}) $ {VP}) -> ((der (Hund) $ {VP}) -> ... - > ((der (Hund) ((Kicks) (das $ {NP})))) -> ((der (Hund) ((Kicks) (der (Hund)))))

Und dann Pop zurück

((der (Hund) ((Kicks) (das $ {N})))) -> ((der (Hund) ((Kicks) (der (Fisch)))))

und wenig später ...

((der (Hund) ($ {V} $ {N}))) -> ((der (Hund) ((erfüllt) $ {N}))) -> ((der (Hund) (( die (Hund)))) erfüllt)

etc.

Im Wesentlichen eine Tiefen ersten Graphen suchen, nur Sie bauen die Grafik, wie Sie es suchen (und Sie Teile stoppen bauen, die die Einschränkungen überschreiten).

Answer 3

Diese Frage enthält einen Kategorienfehler. Die Grammatik von Ihnen angegebenen hat das Aussehen einer kontextfreien Grammatik, aber die Forderung, dass es eine bestimmte Anzahl von Endknoten sein erfordert eine rekursiv aufzählbar Grammatik.