準Thueシステムも，われわれの定式化した理論と見なせる。
ここで準Thueシステムとは，組T＝（Ｌ,α,π）で，つぎの条件を満たすもののことである：
- Ｌは，記号の有限集合でアルファベットと呼ばれる。
- αは，公理と呼ばれる一つの空でない記号列。
- πは，準Thueプロダクションの有限集合。但し準Thueプロダクションとは，記号列ｘ，ｙに対するｘ→ｙの形のプロダクション（即ち，文脈自由にｘをｙで置き換えることを許すプロダクション）のこと。
T＝(Ｌ,α,π) は，つぎのようにして，理論
T′＝(G,H,(S,D),(
S,
D))
と見なせる：
-
G＝(NＶ,TＶ,Ｐ,SEN) は，
-
HはGに同じ。
-
S＝(
G,σ,
R) では，
-
G＝(
NＶ,
TＶ,
Ｐ,
SEN) は，
NＶ＝{
SEN，
SVR}(註)
TＶ＝Ｌ∪{φ,1}
Ｐ：
SEN →SENｘ （ｘ∈Ｌ）
SEN →ε
SEN →SEN SVR
SVR →SVR1
SVR →φ
-
σ：
-
代入規則は原初的代入規則。
-
D＝(φ, {ε→α}∪π)。
-
Sは，
S#＝(
G#,σ#,R＃) の
G#に対し，終端記号に
txt
を追加し，プロダクションに
を追加したもの。
-
Dは，D#。
このように定義したT′に関する証明，定理は，確かに，Tに関する証明，定理と同じものになる。
（註） SVR は,“Sentence-VaRiable"。
|