3

次のようなおもちゃの文法があるとします: (出力がより自然に見えるように更新されます)

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

例：「犬が赤い魔法使いを蹴る」、「鳥が斑点のある魚に出会う、または魔法使いが縞模様の犬と結婚する」

合計n 個のVs + As + Nsを含まなければならないという制約に従って、この文法からどのように文を作成できますか。整数を指定すると、センテンスにはその数の端末が含まれている必要があります。(もちろん、この文法では可能な最小のnは 3 です)。

4

3 に答える 3

3

次の Python コードは、指定された端末数でランダムな文を生成します。これは、指定された長さの文を生成する方法の数を数え、大きな乱数を生成し、指定された文を計算することによって機能します。カウントは、メモ化を使用して再帰的に行われます。空の右辺は、n が 0 の場合は 1 文、それ以外の場合は 0 文を生成します。空でない右辺によって生成される文の数を数えるには、右辺の最初の記号によって使用される端子の数 i を合計します。各 i について、右辺の残りの可能性の数に最初のシンボルの可能性の数を掛けます。最初のシンボルが端子の場合、i が 1 の場合は 1 の可能性があり、それ以外の場合は 0 の可能性があります。最初の記号が非終端記号の場合、各選択肢の可能性を合計します。無限ループを回避するには、数量が 0 の場合に再帰呼び出しを削除するように注意する必要があります。文法に 1 つの文の派生が無限にある場合、これは依然として無限ループになる可能性があります。たとえば、文法では

S -> S S
S ->

空文の派生は無数にあります: S => 、 S => SS => 、 S => SS => SSS => など。特定の文を見つけるコードは、それらをカウントするコードを単純に修正したものです。 . このコードはかなり効率的で、それぞれ 100 個の端末で 100 個のセンテンスを 1 秒未満で生成します。

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))
于 2009-06-08T21:23:15.973 に答える
0

この質問にはカテゴリエラーが含まれています。指定した文法は文脈自由文法のように見えますが、特定の数のターミナルノードが存在するという要件には、帰納的可算文法が必要です。

于 2009-06-09T18:08:17.433 に答える