语法幺半群

维基百科,自由的百科全书
跳转至: 导航搜索

语法幺半群,即在数学中,形式语言 L语法幺半群 M(L) 是可识别语言 L 的最小的幺半群

语法商[编辑]

给定幺半群 M 的子集 S\subset M,可以定义由 S 中元素的形式左逆或右逆组成的集合。它们叫做,可以定义右商和左商,依赖于串接的是哪一端。S 与一个元素 m\in M右商是集合

S/m=\{u\in M \;\vert\; um\in S \}

类似的,左商

m\setminus S=\{u\in M \;\vert\; mu\in S \}

语法等价[编辑]

语法商引发了 M 上的一个等价关系,叫做(引发自 S 的)语法关系语法等价语法同余。右语法等价是等价关系

\sim_S \;= \{(s,t)\in M\times M \,\vert\; S/s = S/t \}

类似的,左语法关系是

\,_S\sim \;= \{(s,t)\in M\times M \,\vert\; s\setminus S = t \setminus S \}

两端同余可以定义为

u \sim_S v \Leftrightarrow \forall x, y\in M (xuy \in S \Leftrightarrow xvy \in S)

语法幺半群[编辑]

语法商相容于在幺半群中的串接,有着

(M/s)/t = M/(ts) \,

对于所有 s,t\in M (左商也类似)。所以,语法商是幺半群态射,并包括一个商幺半群

M(S)= M / \sim_S \,

可以证明 S 的语法幺半群是可识别 S 的最小的幺半群;就是说 M(S) 识别 S,对于所有识别 S 的幺半群 NM(S) 是 N子幺半群的商。S 的语法幺半群也是 S极小自动机转移幺半群

等价的说,一个语言 L 是可识别的,当且仅当商的族

\{L/m \,\vert\; m\in M\}

是有限的。等价性的证明非常容易。假定字符串 x 是可被确定有限状态自动机识别的,带有最终机器状态是 f。如果 y 是这个机器可识别的另一个字符串,也终止于同样的最终状态 f,则明显的有 L/x\,\sim L/y。类似的,在 \{L/m \,\vert\; m\in M\} 中元素的数目就精确等于这个自动机的最终状态的数目。假定反过来: 在 \{L/m \,\vert\; m\in M\} 中元素的数目是有限的。可以接着构造一个自动机,使得 Q=\{L/m \,\vert\; m\in M\} 是状态的集合,F=\{L/m \,\vert\; m\in L\} 是最终状态的集合,单元素集合 L 是初始状态,转移函数给出自 (L/x)/y=L/(xy)。明显的这个自动机识别 L。所以语言 L 是可识别的当且仅当集合 \{L/m \,\vert\; m\in M\} 是有限的。

给定表示 S 的一个正则表达式 E,很容易计算 S 的语法幺半群。

例子[编辑]

參考文獻[编辑]

  • Jean-Eric Pin, "Syntactic semigroups", Chapter 10 in "Handbook of Formal Language Theory", Vol. 1, G. Rozenberg and A. Salomaa (eds.), Springer Verlag, (1997) Vol. 1, pp. 679-746