半自動機:在數學和計算機科學中，半自動機或M-act是么半群在集合上的乘 -百科知識中文網

簡介

半自動機是三元組，這裡的是叫做“輸入字母表”的非空集合， Q是叫做“狀態集合”的非空集合，而 T是“轉移函式”，

當狀態集合 Q是有限集合（不是必須的!）的時候，半自動機可以被認為是確定有限自動機，但是沒有“初始狀態” 或“接受狀態”的集合 A。它還可以被認為是沒有輸出只有輸入的有限狀態自動機。

么半群理論的一個主要主張是半自動機等價於act；所以對於任何act，都有一個獨立的半自動機，或反過來說，對於任何半自動機，都有一個獨立的act。這可以如下這樣證實。

設是從字母表生成的自由么半群，（上標* 要被理解為是Kleene星號）；它是由在中字母構成的所有有限長度字元串的集合。

對於所有中的字 w，設是如下遞歸定義的函式，對於所有 Q中的 q:

如果，則，所以空字不改變狀態。

如果是中的字母，則。

如果對於和，則。

設是個集合

集合在函式複合下閉合；就是說，對於所有，有著。它還包含，它是 S上的恆等函式。因為函式複合根據定義是結合性的，集合是么半群：它叫做半自動機的 輸入么半群、 特徵么半群、 特徵半群或 轉移么半群。

變換半群

變換半群或 變換么半群是由集合（通常稱為“狀態集合”），和映射到自身的函式或“變換” 之么半群或半群構成的有序對。此類函式意指中的每個元素均為一映射。若和是這個變換半群的兩個不同函式，則半群乘積可直覺地由函式複合得出，故吾人將定義為。

注意“半群”與“么半群”的使用：有些作者將“半群”與“么半群”視為同義詞。然而此處一個半群不必然包含單位元素；而一個么半群則意指含有單位元素的半群。因為作用於集合上的函式概念永遠包括恆等函式概念在內，亦即施加於集合上時不做任何動作，故變換半群可藉由與恆等函式聯集轉為么半群。

M-acts

設{\displaystyle M}是么半群而{\displaystyle Q}是非空集合。如果存在一個乘法運算

它滿足性質

此處1表么半群之單位元素，並且

，

對所有和，三元組被稱為右 -act或簡稱 右-act。一般而言，表示“ 的元素與的元素的右乘法”。右-act經常寫為。

左-act定義類似，即

並經常表示為。

一個 -act變換半群十分相似，然而的元素本身不必然為函式，它們僅是某個么半群的元素。所以，必須限制的作用與么半群中的乘法一致（亦即，），因為一般而言，對於某個任意此性質可能不成立，保證此一致性可使進行函式複合時不致出問題。

一旦加上這種限制，就可以完全放心的去掉所有括弧，因為么半群乘積和么半群在集合上的作用是完全滿足結合性的。特別是這允許了么半群的元素被表示為計算機科學意義上字母的字元串。這種抽象接著允許談論一般的字元串運算，並最終導致了由字母的字元串構成的形式語言概念。

-act和變換么半群的另一個差異在於，對一個，么半群的兩個相異元素可能決定同樣的Q變換。若我們限制其發生，則 -act與變換么半群便完全相同。

完全變換么半群

完全變換么半群（或 完全變換半群）是所有映射的蒐集。完全變換么半群是自由么半群，在允許所有可能性的意義上。完全變換么半群的一個特殊情況是置換群。

M-同態

M-同態是映射

使得

對於所有和。所有 M-同態的集合通常寫為或。

性質

如果狀態集合 Q是有限的，則轉移函式通常表示為狀態轉移表。在自由群中字元串所驅動的所有可能轉移的構造有一種叫de Bruijn圖的圖形描述。

狀態集合 Q不需要是有限的。作為例子，半自動機鞏固了量子有限自動機的概念。它的狀態集合 Q由復投影空間給出，單獨狀態別稱為 n-狀態qubit。狀態轉移給出自酉 n× n矩陣。輸入字母表仍是有限的，而其他自動機理論的典型關鍵概念仍有效。因此， 量子半自動機可簡單的定義為三元組當字母表有 p個字母的時候，所以對每個字母都有一個酉矩陣。這種方式規定之後，量子半自動機明顯有多種幾何推廣。比如，可以用黎曼對稱空間替代，並從它的等距群選出轉移函式。

形式語言的語法么半群同構於到接受這個語言的極小自動機的轉移么半群。

範疇Act

定義右作用的代數關係形成了一個範疇 Act。對象是 M-act，而範疇的態射是 M-同態。

半自動機

簡介

變換半群

M-acts

完全變換么半群

M-同態

性質

範疇Act

相關詞條

自動機的半群理論

自動機論

自動機

半群

麼半群

帶零半群

自由麼半群

有限半群

俄APS5.66mm水下突擊步槍

相關搜尋

熱門詞條