TOC 中产品的基本属性是什么？

很容易看出，对于任何语言 L，以下简单属性都成立 -

L · {∧} = {∧} · L = L

L · ∅ = ∅ · L = ∅

现在让我们看看连接运算的交换性和结合性。

乘积的性质 - 交换性

连接运算不是交换的。换句话说，顺序很重要！

给定两个语言 L 和 M，通常情况下

L · M ≠ M · L

示例

如果 L = {ab, ac} 且 M = {a, bc, abc}，则乘积

L · M 是语言

L · M = {aba, abbc, ababc, aca, acbc, acabc},

但乘积 M · L 是语言

M · L = {aab, aac, bcab, bcac, abcab, abcac}

这些没有共同的字符串！

乘积的性质 - 结合性

连接运算具有结合性。换句话说，如果 L、M 和 N 是语言，则

L · (M · N) = (L · M) · N

示例

如果 L = {a, b}，M = {a, aa} 且 N = {c, cd}，则

L · (M · N) = L · {ac, acd, aac, aacd}

= {aac, aacd, aaac, aaacd, bac, bacd, baac, baacd}。

这与以下内容相同：

(L · M) · N = {aa, aaa, ba, baa} · N

= {aac, aacd, aaac, aaacd, bac, bacd, baac, baacd}。

Bhanu Priya

更新于： 2021年6月15日

216 次查看

开启您的 职业生涯

通过完成课程获得认证

开始