从两种语言创建新语言的三种常见方法 -
联盟
路口
产品
语言是字符串的集合,因此它们可以通过通常的并集和交集操作进行组合。
路口
如果 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 是字母 ∑ 上的两种语言。
Concatenation - 字符串的连接操作将两个字符串并置。
字母 ∑ 上两种语言 L1 和 L2 的串联是语言 L 1 L 2 = { wx ∈ ∑* | w ∈ L 1 ∧ x ∈ L 2 }
可以分成两部分的一组字符串 - 一部分来自 L 1,一部分来自 L 2。它类似于两个集合的笛卡尔积,带有字符串。
例子
两个字符串 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 and t ∈ M}