在 TOC 中，對字串執行哪些不同的操作？

字串是從某個字母表中選擇的一組有限的符號序列。

例如：

  • 00011001 是來自二進位制字母表 Σ={0,1} 的一個字串
  • aabbcabcd 是來自字母表 Σ={a,b,c,d} 的一個字串

下面解釋了對字串執行的不同操作：

  • 連線。
  • 子串。
  • 克林閉包運算。
  • 反轉。

連線

連線就是將兩個字串一個接一個地組合起來。

示例

讓我們考慮兩個字串：

X= Tutorials

Y= Point

兩個字串的連線 (X, Y) 為：

X.Y = TutorialsPoint

注意：空字串與其他字串的連線結果為字串本身。

例如，X. ε = ε.X = X

子串

如果 'w' 是一個字串，那麼 'v' 是 'w' 的子串，如果存在字串 x 和 y 使得 w=xvy

'x' 稱為 '字首'，y 稱為 w 的字尾。

示例

讓我們考慮 w='Theory'，它定義了字首 x='The' 和字尾 y='ry'。

子串是 v='o'，因為 w=xvy 並且 Theory= Thevry

因此，v=o

克林閉包運算

設 'w' 為一個字串。w* 是透過將 w 與自身進行任意次數的連線（包括空字串）獲得的字串集合。

示例

a*= { ε,a,aa,aaa,………}

反轉運算

如果 'w' 是一個字串，那麼 wR 是該字串的反轉（倒序）。

規則

反轉運算的規則如下：

  • x=(xR)R
  • (xz)R= zR.xR

示例

字串 x 定義為 x= tutorial，則 (xR)R 為 tutorial。這是因為：

X= tutorial

(x)R= lairotut

(xR)R= tutorial

更新於：2021年6月11日

5K+ 次瀏覽

開啟你的職業生涯

透過完成課程獲得認證

開始學習
廣告