OSAと文法の関係

順序ソートされた代数(OSA)と文法(特に文脈自由文法)の間には何らかの関係がありますか?

私が誤解していないとすれば、[1]によれば、順序ソートされた代数(MSA)と同等のものが存在する(同形まで同じである)ので、MSAと
文法。

[1] Goguen、Joseph A.、Jose
Meseguer。順序ソート代数。オックスフォード大学。コンピューティングラボプログラミング研究グループ、1989年。

ベストアンサー

私は自分の質問に対する答えを[2]で見つける:

$ G = langle N、 Sigma、P rangle $を文脈自由文法とする。私たちは$ G
$を並べ替えられた代数にすることができます。

$$ n w 、} w n w n $$ (N cup Sigma)^ * $で、$
N ^ * times N $ソートファミリー($ operatorname {nt}( alpha)$は$ alpha
)。

最初の$ G $ – 代数は、文法のすべての派生物の解析木を含んでいます。

逆に、$ Sigma $が$ S $にソートされた演算子ドメインである場合、文法を用いて前の構成で得られた初期代数

$$ sigma (s_1 cdots s_n))、 mid( hat { Sigma}} 、
sigma in Sigma {s_1 cdots s_n、s} 、} $$

最初の$ Sigma $ -algebraと同型である。


[2] Goguen、Joseph A.、et al。 “初期代数セマンティクスと連続代数。” Journal of the
ACM(JACM)24.1(1977):68-95。

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です