【正文】 L0 ∪ L+ ? 語言學家 Chomsky(喬姆斯基 )最早從產生語言的角度研究語言 。 1956年 ， 通過抽象 ，Chomsky將語言形式地定義為由一個字母表的字母組成的一些串的集合：對于任意語言 L， 有一個字母表 ， 使得 LC∑*。 可以在字母表上按照一定的形成規(guī)則定義一個文法 ， 該文法產生的所有的句子組成的集合就是該文法產生的語言 。 ? 1959年 ， Chomsky根據(jù)產生語言的文法的產生式的不同特點 ， 將文法和對應產生的語言分為三大類 。 ? 數(shù)學家 Kleene（ 克林 ） 在 1951~1956年間 ，從識別語言的角度來研究語言 ， 給出了語言的另一種描述方式 。 Kleene在研究神經(jīng)細胞時建立了自動機模型 ， Kleene使用該模型來識別 （ 接收 ） 一個語言：按照某種識別規(guī)則構造自動機 ， 該自動機就定義了一個語言 ， 該語言由自動機能夠識別的所有字符串構成 。 ? 語言的兩種不同的定義方式進一步引起了人們的研究興趣 。 一個語言 ， 可以采取不同的描述方式：文法產生語言和自動機識別語言 。 由于是同一個語言 ， 兩種方式應該是等價的 ， 也就存在兩種方式之間的等價的相互轉換方法 。 ? Chomsky于 1959年 ， 將他本人的形式語言的研究成果和 Kleene的自動機的研究成果結合起來 ， 不僅確定了文法和自動機分別從產生和識別角度定義語言 ， 而且證明了文法與自動機的等價性 。 此時 ， 形式語言與自動機理論才真正誕生 。 并被置于數(shù)學的光芒之下 。 ? 形式語言與自動機理論出現(xiàn)后 ， 迅速在計算機科學技術領域得到了應用 。 使用巴科斯 諾爾范式 （ BNFBackusNaur Form） 成功地對高級程序設計語言 ALGOL60的詞法和語法規(guī)則進行了形式化的描述 （ 實際上 ， 巴科斯 諾爾范式就是上下文無關文法的產生式另一種表示方式 ） 。這一成功 ， 使得形式語言與自動機理論得到了進一步的發(fā)展 。 ? 尤其是上下文無關文法 ， 被作為計算機程序設計語言語法的最佳近似描述得到了較為深入的研究 。 后來 ， 人們又將上下文無關文法應用到了模式匹配和模型化處理等方面 ， 而這些內容都是算法描述和分析 、計算復雜性理論和可計算性理論的研究基礎 。 ? 形式語言理論的研究對象與以前的所有語言研究不同 ， 不止自然語言 ， 而是人類一切語言：既有自然語言 ， 也有人工語言 ，包括計算機編程的高級語言 。 喬姆斯基的形式語言理論得到了多重驗證 ， 于是才為語言學界和計算機科學界所折服 ， “ 引發(fā)了語言學中伽利略式的科學革命的開端 。 ” ? 喬姆斯基的形式語言理論得到過計算機科學的三種驗證 。 ? 驗證一：喬氏 4型文法與 4種語言自動機一一對應 。 ? 驗證二：計算機所使用的各種高級語言 ， 如ALGOL、 FORTRAN、 PASCAL、 C、 LISP 等 ，都遵循一種程序語言文法描述的范式 ， 即巴科斯 —諾爾范式 。 計算機科學家發(fā)現(xiàn) ， 巴科斯 —諾爾范式等價于喬姆斯基的 2型文法 ， 即與上下文無關文法 。 而喬姆斯基的 3型文法 ——正則文法 ， 在研究文字的計算機模式識別時 ， 也被有效應用 。 于是 ， 喬氏的 4種類型文法被計算機科學界稱作喬姆斯基分類 。 ? 驗證三：喬姆斯基用形式語言理論的思想證明了計算機科學的一個重大理論問題：計算機程序語言是否有歧義性是不可判定的 。 ? 20世紀中期 ， 程序語言 ALGOL60問世不久 ， 人們發(fā)現(xiàn)它有歧義性 。 當計算機科學家絞盡腦汁尋找辦法來判斷一種程序語言是否有歧義性時 ， 喬姆斯基用形式語言理論的思想證明 ， 一個任意的上下文無關文法是否有歧義性是不可判定的 ， 因此 ， 屬于上下文無關文法的程序語言是否有歧義性也是不可判定的 。 喬姆斯基的論證令計算機科學界折服 。 ?實際上 ， 形式語言與自動機理論除了在計算機科學與技術領域的直接應用外 ， 更在計算機計算機科學與技術領域的人才的計算思維能力的培養(yǎng)中占有極其重要的地位 。 ? 計算機科學與技術學科強調 4個方面的專業(yè)能力：計算思維能力、算法設計與分析能力、程序設計與實現(xiàn)能力、計算機系統(tǒng)的認知、分析、設計和運用能力。這也是計算機科學與其他學科的重要區(qū)別。相關的理論是計算機學科的基礎。 ? 理論方面的知識是計算機的真正靈魂。 ?在本科階段的學習過程中，學生以觀察、描述、比較、分類、推斷、應用、創(chuàng)造思維等科學思維過程為主，強調自學的能力 在培養(yǎng)； ?研究生階段，需要對學生進一步進行抽象思維、邏輯思維、創(chuàng)造思維能力的培養(yǎng)。 ?建立物理符號系統(tǒng)并對起實施等價變換是計算機學科進行問題描述和求解的重要手段 。 “ 可行性 ” 所要求的“ 形式化 ” 及其 “ 離散特征 ” 使得數(shù)學成為重要的工具 ， 而計算模型無論從方法還是從工具等方面 ， 都表現(xiàn)出它在計算機上科學中的重要作用 。 ?計算機科學與技術學科要求學生具有形式化描述和抽象思維能力 ， 要求掌握邏輯思維方法 。 這種能力就是計算思維能力或計算機思維能力 。 ?計算機學科系統(tǒng)地研究信息描述和變換算法 ， 重要包括信息描述和變換算法的理論 、 分析 、 效率 、 實現(xiàn)和運用 。學科的根本問題在于：什么能被 （ 有效地 ） 自動化 ？ 學科的重要內容之一是研究計算領域中的一些普遍規(guī)律 ，描述算法的基本概念與模型 。 ?計算思維能力的培養(yǎng)主要是通過基礎理論系列課程實現(xiàn)的，該系列是由數(shù)學和抽象度較高的理論課程組成，包括數(shù)學分析、集合和圖論、形式語言與自動機、近世代數(shù)、數(shù)學建模等課程。 練習 (見習題 ) ?3(2) ?4 3 給出下列對象的遞歸定義 對于任意 x ? ?*,字符串 x的倒序 (1) 若 |x| 2， 則 xT = x (2) 若 |x| 1， 令 x = ya， 其中 y ? ?+, a ? ?， 則 xT = ayT 4． ?＝ {0， 1}，請給出語言的形式表示 ?所有以 0開頭的串的語言。 ?所有以 0開頭，以 1結尾的串的語言。 ?所有以 11開頭， 11結尾的串的語言。 ?所有最多有一對連續(xù)的 0或者最多有一對連續(xù)的 1的串的語言。 ?所有長度為偶數(shù)的串的語言。 ?所有長度為奇數(shù)的串的語言。 ?所有包含子串 01011的串的語言。 ?所有包含 3個連續(xù) 0的串的語言。 ?所有 的 第 10個字符是 0的串的語言。 ?所有倒數(shù)第 6個字符是 0的串的語言。 習題評講 (續(xù) ) ? 4 (1) {0}{0, 1}* (2) {0}{0, 1}* {1} (3) {11}{0, 1}*{11} ∪ {111， 11} (4)? 習題評講 (續(xù) ) (5) {{0, 1}{0, 1}}* (6) {{0, 1}{0, 1}}* {0, 1} (7) {0, 1}*{01011} {0, 1}* (8) {0, 1}*{000}{0, 1}* 習題評講 (續(xù) ) (9) {0, 1}9 {0}{0, 1}* (10) {0, 1}* {0} {0, 1}5 小結 ?復習 集合、關系、圖 等相關知識 ?引入 形式語言 基本概念