在 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 的連線是語言 L1L2 = { wx ∈ ∑* | w ∈ L1 ∧ x ∈ L2 }

可以拆分為兩部分的字串集 - 一部分來自 L1,另一部分來自 L2。它類似於兩個集合的笛卡爾積,使用字串。

示例

兩個字串 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}

更新於:2021年6月15日

829 次檢視

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告