【正文】 a1a2… an。 ⑸ 單位元素： εx=xε=x。 基本概念 ?前綴與后綴 設(shè) x， y， z， w， v∈ ∑*，且 x=yz， w=yv (1) y是 x的前綴 (prefix)。 (2)如果 z≠ε， 則 y是 x的真前綴 (proper prefix)。 (3) z是 x的后綴 (suffix)； (4) 如果 y≠ε， 則 z是 x的真后綴 (proper suffix)。 (5) y是 x和 w的公共前綴 (mon Prefix)。 基本概念 ?公共 前綴與后綴 (6)如果 x和 w的任何公共前綴都是 y的前綴，則 y是 x和 w的最大公共前綴。 (7) 如果 x=zy， w=vy，則 y是 x和 w的公共后綴 (mon suffix )。 (8)如果 x和 w的任何公共后綴都是 y的后綴，則 y是 x和 w的最大公共后綴。 基本概念 ? 例 字母表 ∑={a， b}上的句子 abaabb的前綴 、 后綴 、 真前綴和真后綴如下： 前綴： ε， a， ab， aba， abaa， abaab， abaabb 真前綴： ε， a， ab， aba， abaa， abaab 后綴： ε， b， bb， abb， aabb， baabb， abaabb 真后綴： ε， b， bb， abb， aabb， baabb 基本概念 ? 結(jié)論 ⑴ x的任意前綴 y有惟一的一個后綴 z與之對應(yīng) ， 使得x=yz；反之亦然 。 ⑵ x的任意真前綴 y有惟一的一個真后綴 z與之對應(yīng) ， 使得 x=yz；反之亦然 。 ⑶ |{w|w是 x的后綴 }|=|{w|w是 x的前綴 }|。 ⑷ |{w|w是 x的真后綴 }|=|{w|w是 x的真前綴 }|。 ⑸ {w|w是 x的前綴 }={w|w是 x的真前綴 }∪ {x}， |{w|w是 x的前綴 }|=|{w|w是 x的真前綴 }|+1。 基本概念 ? 結(jié)論 ⑹ {w|w是 x的后綴 }={w|w是 x的真后綴 }∪ {x}， |{w|w是 x的后綴 }|=|{w|w是 x的真后綴 }|+1。 ⑺ 對于任意字符串 w， w是自身的前綴 ， 但不是自身的真前綴； w是自身的后綴 ， 但不是自身的真后綴 。 ⑻ 對于任意字符串 w， ε是 w的前綴，且是 w的真前綴； ε是 w的后綴，且是 w的真后綴 基本概念 ? 約定 ⑴ 用小寫字母表中較為靠前的字母 a， b，c， … 表示字母表中的字母 。 ⑵ 用小寫字母表中較為靠后的字母 x， y，z， … 表示字母表上的句子 。 ⑶ 用 xT表示 x的倒序。例如，如果 x=abc，則xT=cba。 基本概念 ? 子串 (substring) – w， x， y， z∈ ∑*，且 w=xyz，則稱 y是 w的 子串。 ? 公共子串 (mon substring) – t， u， v， w， x， y， z∈ ∑*，且 t=uyv， w=xyz，則稱 y是 t和 w的 公共子串 (mon substring)。如果 y1， y2， …… ， yn是 t和 w的公共子串，且max{|y1|， |y2|， … ， |yn|}=|yj|，則稱 yj是 t和 w的最大公共子串。 – 兩個串的最大公共子串并不一定是惟一的。 基本概念 ? 語言 (language) ?L?∑*， L稱為字母表 ∑上的一個 語言(language)， ?x∈ L， x叫做 L的一個句子。 ? 例： {0， 1}上的不同語言 {00， 11} ， {0， 1} {0， 1， 00， 11} ， {0， 1， 00， 11， 01， 10} {00， 11}*， {01， 10}*， {00， 01， 10， 11}*， {0}{0， 1}*{1}， {0， 1}*{111}{0， 1}* 基本概念 ? 語言的 乘積 (product) L1?∑1*， L2?∑2*， 語言 L1與 L2的 乘積 是一個語言 ， 該語言定義為： L1L2={xy| x∈ L1， y∈ L2} 是字母表 ∑1∪ ∑2上的語言。 基本概念 ? 例 ⑴ L1={0， 1}。 ⑵ L2={00， 01， 10， 11}。 ⑶ L3={0， 1， 00， 01， 10， 11， 000， … }=∑+ 。 ⑷ L4={ε， 0， 1， 00， 01， 10， 11， 000， … }=∑* 。 ⑸ L5={0n|n≥1}。 ⑹ L6={0n1n|n≥1}。 ⑺ L7={1n|n≥1}。 ⑻ L8={0n1m|n， m≥1}。 ⑼ L9={0n1n0n|n≥1}。 ⑽ L10={0n1m0k|n， m， k≥1}。 ⑾ L11={x|x∈ ∑+且 x中 0和 1的個數(shù)相同 }。 基本概念 ?上述幾個語言的部分特點及相互關(guān)系 上述所有語言都是 L4的子集 (子語言 )； L1， L2是有窮語言；其他為無窮語言；其中 L1是 ∑上的所有長度為 1的句子組成的語言 ， L2是 ∑ 上的所有長度為 2的句子組成的語言； L3， L4分別是 ∑ 的正閉包和克林閉包； L5L7≠ L6，但 L5L7= L8；同樣 L9≠ L10，但是我們有： L6?L5L7， L9?L10。 基本概念 L6={0n1n|n≥ 1}中的句子中的 0和 1的個數(shù)是相同的 ， 并且所有的 0在所有的 1的前面 ，L11={x|x∈∑ +且 x中 0和 1的個數(shù)相同 }中的句子中雖然保持著 0的個數(shù)和 1的個數(shù)相等 ，但它并沒要求所有的 0在所有的 1的前面 。例如 ， 0101， 1100∈ L11， 但是 0101? L6，1100?L6。 而對 ?x∈ L6， 有 x∈ L11。 所以 ，L6 ?L11。 基本概念 L1?L12， L2?L12 L5?L12， L6?L12 L7?L12， L8?L12 L9?L12， L10?L12 L1?L10， L2?L10 L5?L10， L6?L10 L7?L10， L8?L10 L9?L10， L10?L12 基本概念 ? 例 ⑴ {x|x=xT， x∈∑ }。 ⑵ {xxT|x∈∑ +}。 ⑶ {xxT|x∈∑ *}。 ⑷ {xwxT|x， w∈∑ +}。 ⑸ {xxTw|x， w∈∑ +}。 基本概念 ? 冪 ?L∈∑ *， L的 n次 冪 是一個語言，該語言定義為 ⑴ 當(dāng) n=0是， Ln={ε }。 ⑵ 當(dāng) n≥ 1時， Ln= Ln1L 。 ? 正閉包 L+=L∪ L2∪ L3∪ L4∪ … ? 克林閉包 L*= L0∪ L∪ L2∪ L3∪ L4∪ … 小結(jié) 本章簡單敘述了一些基礎(chǔ)知識，一方面，希望讀者通過對本章的閱讀，熟悉集合、關(guān)系、圖、形式語言等相關(guān)的一些基本知識點，為以后各章學(xué)習(xí)作適當(dāng)?shù)臏?zhǔn)備。另一方面，也使讀者熟悉本書中一些符號的意義。 小結(jié) (1) 集合：集合的表示 、 集合之間的關(guān)系 、 集合的基本運算 。 (2) 關(guān)系：主要介紹了二元關(guān)系相關(guān)的內(nèi)容 。包括等價關(guān)系 、 等價分類 、 關(guān)系合成 、 關(guān)系閉包 。 (3) 遞歸定義與歸納證明 。 小結(jié) (4) 圖：無向圖 、 有向圖 、 樹的基本概念 。 (5) 語言與形式語言：自然語言的描述 ， 形式語言和自動機理論的出現(xiàn) ， 形式語言和自動機理論對計算機科學(xué)與技術(shù)學(xué)科人才能力培養(yǎng)的作用 (6) 基本概念：字母表 、 字母 、 句子 、 字母表上的語言 、 語言的基本運算