正則置換關係

正則置換是形式語言理論和語言代數理論方面的一種特殊置換。3型語言對正則置換具有封閉性。

基本介紹

• 中文名：正則置換關係
• 外文名：regular permutation
• 別名：正則置換
• 領域：語言代數理論

約定記號

表示一個有窮字母表， 表示由有窮字母表 生成的自由半群。

設 ， 是有窮字母表 上的兩個語言，我們用 表示 與 的連線，即 。

準備概念

3型文法或稱正則文法，生成式的形式為A→wB或A→w,A,B∈N,w∈T* 稱右線性文法;如果生成式的形式為A→Bw或A→w, 則稱左線性文法。由正則文法產生的語言稱為正則語言。

定義

定義1

設 是定義在有窮字母表 上的一個映射，使得對於任意的 ， 是有窮字母表 上的一個語言。我們按照如下的規則將映射 的定義域擴充為 ：

其中 表示空字，P,Q ，稱如此得到的由 到 的映射 ，其中 ，是一個置換。

定義2

設 是從有窮字母表 生成的自由半群 到有窮字母表 生成的自由半群 的冪集 的置換，若對於每個 ，均使 是一個3型語言，則稱 是從 到 的正則置換。

舉例

S置換是一類特殊的正則置換。

S置換定義

設 是從有窮字母表 生成的自由半群 到有窮字母表 生成的自由半群 的冪集 的置換，若 使得集合類 是集合 的一個分劃，則稱置換 為一個S置換。

定理1

（封閉性）設 是從有窮字母表 生成的自由半群 到有窮字母表 生成的自由半群 的冪集 的S置換，若L是 上的一個3型語言，則 也是3型的。

定理2

（充分性）設 是從有窮字母表 生成的自由半群 到有窮字母表 生成的自由半群 的冪集 的S置換，則 是正則的。

正則置換的一種表達式

定理：關於V上任何正則置換f，常存在V上的置換，使得。

（中一切S置換：生成的子代數記為，其中。）