二つの文生成変形システム
Ti＝(Gi,Gi,(Si,Di))(註1) (i＝1,2)
が同型であることを，以下の条件を満たすことと定義する。
即ち，
Gi＝(NＶi,TＶi,Ｐi,Ｓi)，
Si＝(Gi,σi,Ri)，
Gi＝(NＶi,TＶi,Ｐi,Ｓi)，
Di＝(ＶDi,ＰDi)
|
（i＝1,2）
|
とするとき，
- G1とG2の間の（文生成システムの）同型ｆ＝(ｆN,ｆT）
- G1とG2の間の（文生成システムの）同型ｆ＝(ｆN,ｆT）
- １対１対応 ｄ:ＶD1─→ＶD2
で，つぎの条件を満たすものがとれる：
(1) ｆは，G1とG2の間の同型を導く。
(2) つぎの二つの図式はともに可換：
(3) ｆNとｆNは，代入規則の間の１対１対応を導く；
(4) ｆとｄは，１対１対応 ＰD1─→ＰD2 を導く(註2)
また，このときのｆ，ｆ,ｄの組（ｆ,ｆ,ｄ）を，T1のT2の上への同型と呼ぶ。
（註１） 文生成変形システム (G,H,(S,D))において，GとHは同値な文生成システムなので，Gは最初からHとしてとられていると考えてよい。したがって，G＝Hとして一般性を失わない。
（註２） 即ち，Ｍi＝TＶi∪ＶDi（i＝1,2）に対し，Ｍ1のＭ2の上への１対１対応ｈが，
ｈ｜TＶ1 ＝ｆT
ｈ｜TＶ1＝ｆT
ｈ｜ＶD1 ＝ｄ
|
で定義され，さらに
ｈ*：Ｍ1*＼{ε}─→Ｍ2*
が，つぎのように定義される：
ｈ*(ｘ1ｘ2････ｘn) ＝ｈ(ｘ1)ｈ(ｘ2)････ｈ(ｘn)
（ｘ1,････,ｘn∈Ｍ1）
このとき，ｈ*｜ＰD1がＰD1とＰD2の間の１対１対応になっていること。
|