波斯特系統(Post system)亦稱波斯特正規系統或組合系統，一種形式系統，它是由波蘭一美國數理邏輯學家波斯特(Post,E. L.)於20世紀20年代研究並在1943年發表的。
基本介紹
- 中文名：波斯特系統
- 外文名：Post system
簡介：它在形式上與邏輯中的形式系統十分相像，具體地，所謂波斯特系統PS，包括一個字母表藝(其中的常元和變元分別組成二和v，且=yUv＞ ,上的字組成的有窮公理集s(S中字也稱原始假設)和一個有窮的產生程式屍，屍中的元素為形如(al,aZ,...,a a)的n元產生式(W為某個自然數)；其中a都是藝上的字，這種產生式記為al,aZ,...,an-＞ a.在運用此產生式時，先把諸a中的變元都用藝。中的字一致地替代(即同一變元用相同的字替代)，這樣便得到反，，反2，…，吞，，。.此時可依產推出“a.若aEW，並且從PS的公理S出發，有窮多次運用P中的產生式可以推出Q，則稱Q為PS的一個定理.PS的全體定理組成波斯特系統PS產生的語言LIPS)一個語言L可以被某個波斯特系統產生，若且唯若L為遞歸可枚舉的。
實際上，在波斯特系統中，可以限定所有的產生式都形如uA-＞ Aw，其中A為變元，u,wE乏‘，並約定只有一條初始假設，它們仍能產生所有遞歸可枚舉的語言。即對波斯特系統的這種限制並沒有減弱波斯特系統的力量，因此，在許多情形，波斯特系統被定義成這種受限制的形式。這種系統稱為正規系統.它們實際上是由布契(Buchi,J. R.)於1964年首先引進的.但是，如果進一步把產生式限制到形如:A-＞ wA(稱為右正則的)或限制到Au-＞ Aw(稱為左正則的)時，就只能產生出正規語言類(參見“喬姆斯基分層”)，而不能產生出全體遞歸可枚舉語言來。此時，它們的力量僅與有窮自動機相當。
