【文章內(nèi)容簡介】 閉包 ? 閉包 (closure) – 設 P是關于關系的性質(zhì)的集合，關系 R的 P閉包(closure)是包含 R并且具有 P中所有性質(zhì)的最小關系 。 ? 正閉包 (positive closure) (1)R?R+。 (2)如果 (a， b)， (b， c)∈ R+ 則 (a， c)∈ R+。 (3)除 (1)、 (2)外 ， R+不再含有其他任何元素 。 關系的閉包 ?傳遞閉包 (transitive closure) – 具有傳遞性的閉包 。 – R+具有傳遞性 。 ?可以證明 ， 對任意二元關系 R， R+= R∪ R2∪ R3∪ R4∪ … ?而且當 S為有窮集時： R+= R∪ R2∪ R3∪ … ∪ R|S| 關系的閉包 ?克林閉包 (Kleene closure) R* (1) R0? R*,R? R*。 (2) 如果 (a， b)， (b， c)∈R * 則 (a， c)∈R *。 (3) 除 (1)、 (2)外， R*不再含有其他任何元素。 ?自反傳遞閉包 (reflexive and transitive closure) R*具有自反性、傳遞性 。 關系的閉包 ? 可以證明 ， 對任意二元關系 R， R*= R0∪ R+ R* =R0∪ R∪ R2∪ R3∪ R4∪ … ? 而且當 S為有窮集時： R*= R0∪ R∪ R2∪ R3∪ … ∪ R|S| 關系的閉包 ? R R2是 S上的兩個二元關系 (1) Φ+=Φ。 (2) (R1+)+= R1+ 。 (3) (R1*)*= R1*。 (4) R1+∪ R2+?(R1∪ R2)+。 (5) R1*∪ R2*?(R1∪ R2)*。 圖 ? 數(shù)學家歐拉 ()解決著名的哥尼斯堡七橋。 ? 直觀地講，圖是由一些點和一些連接兩點的邊組成。 ? 含無方向的邊的圖為無向圖，含帶有方向的邊的圖為有向圖。 無向圖 ? 無向圖 (undirected graph) – 設 V是一個非空的有窮集合， E?V V， G=(V，E)稱為 無向圖 (undirected graph)。其中 V中的元素稱為 頂點 (vertex或 node)， V稱為頂點集，E中的元素稱為 無向邊 (undirected edge)， E為無向邊集。 ? 圖表示 – V中稱為頂點 v的元素用標記為 v的小圈表示， E中的元素 (v1， v2)用標記為 v1， v2的頂點之間的連線表示。 無向圖 ? 路 (path) – 如果對于 0≤i≤k1， k≥1，均有 (vi， vi+1)∈ E，則稱 v0， v1， … ， vk是 G=(V， E)的一條長為 k的路。 ? 回路或圈 (cycle) – 當路 v0， v1， … ， vk中 v0=vk時， v0， v1， … ， vk叫做一個 回路或圈 (cycle)。 無向圖 ? 頂點的度數(shù) – 對于 v∈ V， |{v|(v， w)∈ E}|稱為無向圖 G=(V，E)的頂點 v的度數(shù) ， 記作 deg(v)。 – 對于任何一個圖，圖中所有頂點的度數(shù)之和為圖中邊的 2倍。 ???VvEv ||*2)de g (deg(v1)=3 deg(v2)=3 deg(v3)=4 deg(v4)=3 deg(v5)=3 deg(v1)+deg(v2)+deg(v3)+deg(v4)+deg(v5)=16 無向圖 ? 連通圖 – 如果對于 ?v， w∈ V， v≠w， v與 w之間至少有一條路存在，則稱 G=(V， E)是 連通圖 。 – 圖 G是連通的充要條件是 G中存在一條包含圖的所有頂點的路。 有向圖 ? 有向圖 (directed graph) – G=(V， E)。 – V： 頂點 (vertex或 node)集。 – (v1， v2)∈ E： 頂點 v1到頂點 v2的 有向邊(directed edge)，或 弧 (arc)， v1稱為 前導(predecessor)， v2稱為 后繼 (successor)。 ? 有向路 (directed path) – 如果對于 0≤ i≤ k1， k≥ 1，均有 (vi， vi+1)∈ E，則稱 v0， v1， … ， vk是 G的一條長為 k的 有向路。 有向圖 ? 有向回路或有向圈 (directed cycle) – 對于 0≤ i≤ k1， k≥ 1，均有 (vi， vi+1)∈ E， 且v0=vk，則稱 v0， v1， … ， vk是 G的一條長為 k的有向路為 一個 有向回路。 –有向回路又叫有向圈。 ? 有向圖的圖表示 – 圖 G的圖表示是滿足下列條件的 “ 圖 ” ：其中 V中稱為頂點 v的元素用標記為 v的小圈表示， E中的元素 (v1， v2)用從標記為 v1的頂點到標記為 v2的頂點的弧表示。 有向圖 ? 頂點的度數(shù) –入度 (數(shù) )： ideg(v)=|{v|(w， v)∈ E}|。 –出度 (數(shù) )： odeg(v)= |{v|(v， w)∈ E}|。 ? 對于任何一個有向圖，圖中所有頂點的入度之和與圖中所有頂點的出度之和正好是圖中邊的個數(shù) ??????VvVvEvovi ||)de g ()de g (兩個不同的有向圖 樹 ? 滿足如下條件的有向圖 G=(V， E)稱為一棵(有序、有向 )樹 (tree)： –根 (root) v： 沒有前導，且 v到樹中其他頂點均有一條有向路。 – 每個非根頂點有且僅有一個前導。 – 每個頂點的后繼按其拓撲關系從左到右排序。 樹 ?樹的基本概念 (1) 頂點也可以成為結(jié)點。 (2) 結(jié)點的前導為該結(jié)點的 父親 (父結(jié)點 father)。 (3) 結(jié)點的后繼為它的 兒子 (son)。 (4) 如果樹中有一條從結(jié)點 v1到結(jié)點 v2的路，則稱v1是 v2的 祖先 (ancestor), v2是 v1的 后代 (descendant)。 (5) 無兒子的頂點叫做 葉子 (leaf)。 (6) 非葉結(jié)點叫做 中間結(jié)點 (interior)。 樹 ? 樹的層 – 根處在樹的第 1層 (level)。 – 如果結(jié)點 v處在第 i層 (i≥ 1)，則 v的兒子處在第i+1層 。 – 樹的最大層號叫做該樹的高度 (height)。 樹 ? 二元樹 – 如果對于 ?v∈ V， v最多只有 2個兒子，則稱G=(V， E)為 二元樹 (binary tree)。 – 對一棵二元樹，它的第 n層最多有 2n1個結(jié)點。一棵 n層二元樹最多有個 2n1葉子。 語言 什么是語言 ? 例如： “ 學大一生是個我 ” ； “ 我是一個大學生 ” 。 ? 語言是一定的群體用來進行交流的工具。 ? 必須有著一系列的生成規(guī)則、理解 (語義 )規(guī)則 。 什么是語言 什么是語言 ? 斯大林：從強調(diào)語言的作用出發(fā)，把語言定義為 “ 為廣大的人群所理解的字和組合這些字的方法 ” 。 ? 語言學家韋波斯特 (Webster) ：為相當大的團體的人所懂得并使用的字和組合這些字的方法的統(tǒng)一體。 ? 要想對語言的性質(zhì)進行研究，用這些定義來建立語言的數(shù)學模型是不夠精確的。必須有更形式化的定義。 形式語言與自動機理論的產(chǎn)生與作用 ? 語言學家喬姆斯基，畢業(yè)于賓西法尼亞大學，最初從產(chǎn)生語言的角度研究語言。1956年，他將語言 L定義為一個字母表 ∑ 中的字母組成的一些