在 TOC 中结合两种语言的技术是什么？

从两种语言创建新语言有三种常见方法：

• 并集

• 交集

• 积

语言是字符串的集合，因此可以通过通常的集合运算（并集和交集）来组合它们。

交集

如果 L1 和 L2 是 ∑ 上的语言，则 L1 ∩ L2 是 L1 和 L2 中字符串的语言。

例如，如果 L = {aa, bb, ab} 且 M = {ab, aabb}，则：

交集如下：

L ∩ M = {ab}

以及

并集

如果 L1 和 L2 是字母表 ∑ 上的语言，则语言 L1 ∪ L2 是至少在两种语言中的一种中的所有字符串的语言。

例如，如果 L = {aa, bb, ab} 且 M = {ab, aabb}，则：

并集如下：

L ∪ M = {aa, bb, ab, aabb}。

其中 L 和 M 是字母表 ∑ 上的两种语言。

连接 - 字符串连接操作将两个字符串并排放置。

字母表 ∑ 上的两种语言 L1 和 L2 的连接是语言 L₁L₂ = { wx ∈ ∑* | w ∈ L₁ ∧ x ∈ L₂ }

可以拆分为两部分的字符串集 - 一部分来自 L₁，另一部分来自 L₂。它类似于两个集合的笛卡尔积，使用字符串。

示例

两个字符串 aab 和 ba 的连接是字符串 aabba。

我们使用名称 cat 来表示此操作 - cat(aab, ba) = aabba。

我们可以通过形成 L 中的字符串与 M 中的字符串的所有连接的集合来组合两种语言 L 和 M，这称为两种语言的积。

定义（两种语言的积）

如果 L 和 M 是语言，则称为 L 和 M 的积的新语言定义为 L · M（或仅 LM）

L · M = {cat(s,t) : s ∈ L 且 t ∈ M}

Bhanu Priya

更新于：2021年6月15日

829 次查看

开启你的 职业生涯

通过完成课程获得认证

开始学习