-2

Prologを使用して、文脈自由文法を認識true し、入力リストが CFG に一致するかどうかを返す述語を作成しようとしています。
入力のアルファベットは のみで構成されていますa,b。私が一致させようとしているCFGは

S-> TT
T -> aTb | ab

これを実装する方法がよくわかりません。主に T ルールです。

s(S0,S):-t(S0,S),t(S1,S).
t(S0,S):-S0 = a, t(S1,S), S1 = b; S0 = a, S1 = b.

match([H|T] :- s(H,T).

したがって、クエリを実行[a, a, b, b]すると、 が返されtrueます。ただし、無限ループが発生しています。a^n b^nルール を実装する方法がよくわかりません。

4

1 に答える 1

3

このように CFG を記述します。

S -> T
T -> a T b | {epsilon}

DCG に直接変換されます。

s --> t.
t --> [].
t --> a, t, b.

フレーズを生成する機能を得るために、イプシロン ルールを交換したことに注意してください。

その DCG を手で翻訳する:

s(S0,S) :- t(S0,S).
t(S0,S0).
t(S0,S) :- S0=[a|S1], t(S1,S2), S2=[b|S].

収量

?- phrase(s,L).
L = [] ;
L = [a, b] ;
L = [a, a, b, b] ;
L = [a, a, a, b, b, b] ;
...
于 2013-05-08T10:29:47.677 に答える