形式語言與自動機理論pdf

『壹』 形式語言與自動機^計算機數學

所謂形式，就是和實物、實際、具體相對而言，是抽象的，純粹理論的。形而上學的「形」，也是這個意思。
基本上，形式語言是以數學描述語言。比如語句最終由「終結符號」組成，這里主要就是集合論的內容；「產生式」，又相當於映射或者函數。
程序設計語言是形式語言，但形式語言的涵義要深、廣。

自動機理論主要是對「通用計算」的抽象。有了對通用計算的描述，使用機械讓計算自動起來就只是一個工程技術上的問題。

基本上說，這些理論背後的數學是離散數學。

『貳』 泵引理（形式語言與自動機理論）正規語言

形式語言 形式語言是一個字母表上的某些有限長字串的集合。一個形式語言可以包含無限多個字串。 語言的形式定義 字母表∑為任意有限集合,ε表示空串,記∑0為{ε},全體長度為n的字串為∑n,∑*為∑0∪∑1∪…∪∑n...

『叄』 有限自動機理論的目錄

第一章基礎知識
1.1集合及其運算
1.2關系
1.2.1二元關系
1.2.2等價關系
1.2.3關系的合成
1.3證明和證明的方法
1.3.1反證法
1.3.2歸納法
1.3.3遞歸的定義與歸納證明
1.4圖與樹
1.5語言
1.6常用術語
1.7形式語言與自動機的發展
習題一
第二章形式語言
2.1例子語言
2.2文法和語言的關系
2.3Chomsky對文法的分類
2.4文法產生語言
2.5推導樹
2.6空串定理
2.7消除左遞歸
2.7.1消除直接左遞歸
2.7.2消除間接左遞歸
2.8上下文無關文法的另一種表示
2.9語言之間的運算及運算的封閉性
2.9.1語言之間的基本運算
2.9.2語言之間的運算的封閉性
2.9.3語言之間的其他運算
2.10正則表達式和正則集
習題二
第三章有限狀態自動機
3.1有限狀態自動機
3.2有限狀態自動機識別的語言
3.3有限狀態自動機識別語言的例子
3.4不確定的有限狀態自動機
3.4.1不確定的有限狀態自動機
3.4.2不確定的有限狀態自動機的確定化
3.5帶有s動作的有限狀態自動機
3.6有限狀態自動機的一些變形
3.6.1雙向的有限狀態自動機
3.6.2帶有輸出的有限狀態自動機
3.7有限狀態接收機的存儲技術
習題三
第四章正則語言
4.1正則語言與有限狀態自動機
4.1.1正則表達式對應有限狀態自動機
4.1.2正則語言的等價模型
4.2正則語言的泵浦引理
4.3正則語言對運算的封閉性
4.4正則語言類中的判定演算法
習題四
第五章下推自動機
5.1下推自動機
5.1.1確定的下推自動機
5.1.2不確定的下推自動機
5.1.3下推自動機接收語言的兩種方式
5.1.4廣義的下推自動機和單態下推自動機
5.1.5下推自動機的存儲技術
5.1.6下推自動機掃描多個符號
5.2上下文無關文法和範式
5.2.1Chomsky範式
5.2.2Greibach範式
5.3下推自動機與上下文無關語言
習題五
第六章圖靈機
參考文獻

『肆』 請問什麼是形式語言與自動機

形式語言
形式語言 是一個字母表上的某些有限長字串的集合。一個形式語言可以包含無限多個字串。

語言的形式定義
字母表 ∑ 為任意有限集合，ε 表示空串， 記 ∑ 0 為{ε}，全體長度為 n 的字串為 ∑ n ， ∑ * 為 ∑ 0 ∪∑ 1 ∪…∪∑ n ∪…， 語言 L 定義為 ∑ * 的任意子集。

注記：∑ * 的空子集 Φ 與 {ε} 是兩個不同的語言。

語言間的運算
語言間的運算就是 ∑ * 冪集上的運算。

字串集合的交並補等運算。
連接運算：L 1 L 2 = { xy | x 屬於L 1 並且 y 屬於L 2 }。
冪運算：L n = L … L （共 n 個 L 連接在一起），L 0 = {ε}。
閉包運算：L * = L 0 ∪L 1 ∪…∪L n ∪…。
（右）商運算：L 1 /L 2 = {x | 存在 y 屬於L 2 使得 xy 屬於L 1 }。
語言的表示方法
一個形式語言可以通過多種方法來限定自身，比如：

枚舉出各個字串（只適用於有限字串集合）。
通過 形式文法 來產生（參見 喬姆斯基譜系 ）。
通過正則表達式來產生。
通過某種自動機來識別，比如 圖靈機 、 有限狀態自動機 。
自動機
automata

對信號序列進行邏輯處理的裝置。在自動控制領域內，是指離散數字系統的動態數學模型，可定義為一種邏輯結構，一種演算法或一種符號串變換。自動機這一術語也廣泛出現在許多其他相關的學科中，分別有不同的內容和研究目標。在計算機科學中自動機用作計算機和計算過程的動態數學模型，用來研究計算機的體系結構、邏輯操作、程序設計乃至計算復雜性理論。在語言學中則把自動機作為語言識別器，用來研究各種形式語言。在神經生理學中把自動機定義為神經網路的動態模型，用來研究神經生理活動和思維規律，探索人腦的機制。在生物學中有人把自動機作為生命體的生長發育模型，研究新陳代謝和遺傳變異。在數學中則用自動機定義可計算函數，研究各種演算法。現代自動機的一個重要特點是能與外界交換信息，並根據交換得來的信息改變自己的動作，即改變自己的功能，甚至改變自己的結構，以適應外界的變化。也就是說在一定程度上具有類似於生命有機體那樣的適應環境變化的能力。
自動機與一般機器的重要區別在於自動機具有固定的內在狀態，即具有記憶能力和識別判斷能力或決策能力，這正是現代信息處理系統的共同特點。因此，自動機適宜於作為信息處理系統乃至一切信息系統的數學模型。自動機可按其變數集和函數的特性分類，也可按其抽象結構和聯結方式分類。主要有：有限自動機和無限自動機、線性自動機和非線性自動機、確定型自動機和不確定型自動機、同步自動機和非同步自動機、級聯自動機和細胞自動機等。

『伍』 計算機科學與技術（專業限選課）~~

我也是計算機科學與技術專業的，也讀大二，冒昧說下自己的看法，呵呵。。
Java語言程序設計：Java是目前最流行的兩個開發環境之一（另一個是微軟的.NET），現在很多軟體，尤其是手機軟體都是由Java寫的，如果你將來從事軟體開發的話這會是很重要的一門技能。
形式語言與自動機理論是關於理論計算機的，理論研究用的。個人覺得你將來如果不專門做計算機方面的研究工作這個是不會用到太多的。
計算機圖形學是非常重要的一門學科，是一種使用數學演算法將二維或三維圖形轉化為計算機顯示器的柵格形式的科學。其實就是研究計算機如何處理和表現圖形的。
單片機原理和介面技術、嵌入式系統都是硬體方面的。前者主要是講單片機的原理製作以及計算機的各種介面，像網卡介面、音效卡介面這些。嵌入式系統就是在某種器件上面集成各種晶元什麼的來完成不同功能。
我也剛入門，懂得不多，見諒啦~~~

『陸』 形式語言與自動機理論（第2版）清華大學出版社的課後答案

第1章 概 述
習題(答案)
一．選擇題
1. D 2. B 3. CD 4. C 5. ABC
6. A 7. B 8. B 9. ABCD 10. ABCDE

二．簡答題
1．什麼是計算機系統？
計算機系統是一種能夠按照事先存儲的程序，自動、高速地對數據進行輸入、處理、輸出和存儲的系統，由計算機硬體系統和計算機軟體系統兩大部分組成。
2．請解釋馮•諾依曼所提出的「存儲程序」概念。
把程序和數據都以二進制的形式統一存放在存儲器中，由機器自動執行。不同的程序解決不同的問題，實現了計算機通用計算的功能。
3．控制器的主要功能是什麼？
控制器基本功能就是從內存中取出指令和執行指令，即控制器按程序計數器指出的指令地址從內存中取出該指令進行解碼，然後根據該指令功能向有關部件發出控制命令，執行該指令。另外，控制器在工作過程中，還要接受各部件反饋回來的信息。
4．簡述CPU和主機的概念。
通常把運算器、控制器做在一個大規模集成電路塊上稱為中央處理器，又稱CPU(Central Processing Unit)。
通常把內存儲器、運算器和控制器合稱為計算機主機，也可以說主機是由CPU與內存儲器組成的，而主機以外的裝置稱為外部設備，外部設備包括輸入/輸出設備，外存儲器等。
5．什麼是計算機軟體？計算機軟體的分類有哪些？
軟體是指用來指揮計算機運行的各種程序的總和以及開發、使用和維護這些程序所需的技術文檔。
計算機軟體系統分為系統軟體和應用軟體。計算機系統軟體由操作系統、語言處理系統、以及各種軟體工具等組成，指揮、控制計算機硬體系統按照預定的程序運行、工作，從而達到預定的目標。應用軟體是用戶利用計算機軟、硬體資源為解決各類應用問題而編寫的軟體，包括用戶程序及其說明性文件資料。
6．計算機有哪些主要的特點？
(1)運算速度快、精度高
計算機的字長越長，其精度越高，現在世界上最快的計算機每秒可以運算幾十萬億次以上。一般計算機可以有十幾位甚至幾十位(二進制)有效數字，計算精度可由千分之幾到百萬分之幾，是任何計算工具所望塵莫及的。
(2)具有邏輯判斷和記憶能力
計算機有準確的邏輯判斷能力和高超的記憶能力。能夠進行各種邏輯判斷，並根據判斷的結果自動決定下一步應該執行的指令。
(3)高度的自動化和靈活性
計算機採取存儲程序方式工作，即把編好的程序輸入計算機，機器便可依次逐條執行，這就使計算機實現了高度的自動化和靈活性。
7．計算機的分類有哪些？
根據計算機工作原理和運算方式的不同，以及計算機中信息表示形式和處理方式的不同，計算機可分為數字式電子計算機(Digital Computer)、模擬式電子計算機(Analog Computer)和數字模擬混合計算機(Hybrid Computer)。當今廣泛應用的是數字計算機，因此，常把數字式電子計算機(Electronic Digital Computer)簡稱為電子計算機或計算機。
按計算機的用途可分為通用計算機(General Purpose Computer)和專用計算機(Special Purpose Computer )兩大類。通用計算機能解決多種類型問題，是具有較強通用性的計算機，一般的數字式電子計算機多屬此類；專用計算機是為解決某些特定問題而專門設計的計算機，如嵌入式系統。
根據計算機的總體規模對計算機分類，可分為巨型機(Super Computer)、大/中型計算機(Mainframe)、小型計算機(Mini computer)、微型計算機(Micro computer)和網路計算機(Network Computer)五大類。
常見的微型機還可以分為台式機、便攜機、筆記本電腦、掌上型電腦等多種類型。
8．簡述計算機的基本運行方式。
計算機的基本運作方式可概括為所謂的「IPOS循環」。IPOS循環即輸入(Input)、處理(Processing)、輸出(Output)和存儲(Storage)，它反映了計算機進行數據處理的基本步驟。
(1)輸入
接受由輸入設備(如鍵盤、滑鼠器、掃描儀等)提供的數據。
(2)處理
對數值、邏輯、字元等各種類型的數據進行操作，按指定的方式進行轉換。
(3)輸出
將處理所產生的結果等數據由輸出設備(如顯示器、列印機、繪圖儀等)進行輸出。
(4)存儲
計算機可以存儲程序和數據供以後使用。
9．計算機有哪些主要的用途？
(1)科學計算
使用計算機來完成科學研究和工程技術中所遇到的數學問題的計算稱為科學計算，也稱為數值計算。科學計算是使用計算機完成在科學研究和工程技術領域中所提出的大量復雜的數值計算問題，是計算機的傳統應用之一。
(2)信息處理
所謂信息處理就是使用計算機對數據進行輸入、分類、加工、整理、合並、統計、製表、檢索以及存儲等，又稱為數據處理。例如座席預訂與售票系統、零售業中的應用、辦公自動化等。信息處理已成為當代計算機的主要任務，是現代化管理的基礎。
(3)實時控制(也稱過程式控制制)
實時控制也稱過程式控制制，實時控制能及時地採集檢測數據、使用計算機快速地進行處理並自動地控制被控對象的動作，實現生產過程的自動化。
(4)計算機輔助設計/輔助製造/輔助教學
計算機輔助設計(Computer Aided Design——CAD)是使用計算機來輔助人們完成產品或工程的設計任務的一種方法和技術。計算機輔助製造(Computer Aided Manufacturing——CAM)是使用計算機輔助人們完成工業產品的製造任務，能通過直接或間接地與工廠生產資源介面的計算機來完成製造系統的計劃、操作工序控制和管理工作的計算機應用系統。計算機輔助教學(Computer Aided Instruction——CAI)是把計算機用作教學媒體，使它充當指導者、工具和學習者角色，學生通過與計算機的對話進行學習的一種新型教學技術。
(5)人工智慧
人工智慧(Artificial Intelligence——AI)就是指計算機模擬人類某些智力行為的理論、技術和應用。
(6)多媒體技術
隨著電子技術特別是通信和計算機技術的發展，人們已經有能力把文本、音頻、視頻、動畫、圖形和圖像等各種媒體綜合起來，構成「多媒體」(Multimedia)的概念。
10．簡述計算機的發展趨勢。
(1)微型化
一方面，隨著計算機的應用日益廣泛，在一些特定場合，需要很小的計算機，計算機的重量、體積都變得越來越小，但功能並不減少。另一方面，隨著計算機在世界上日益普及，個人電腦正逐步由辦公設備變為電子消費品。人們要求電腦除了要保留原有的性能之外，還要有時尚的外觀、輕便小巧、便於操作等特點，如平板電腦、手持電腦等。今後個人計算機(Personal Computer)在計算機中所佔的比重將會越來越大，使用也將會越來越方便。
(2)巨型化
社會在不斷發展，人類對自然世界的認識活動也越來越多，很多情況要求計算機對數據進行運算。「巨型化」在這里並不是通常意義上的大小，主要是指機器的性能——運算速度等。
(3)網路化
網際網路(Internet)的建立正在改變我們的世界，改變我們的生活。網路具有虛擬和真實兩種特性，網上聊天和網路游戲等具有虛擬特性，而網路通信、電子商務、網路資源共享則具有真實的特性。
(4)智能化
今後，計算機在生活中扮演的角色將會更加重要,計算機應用將具有更多的智能特性，能夠幫助用戶解決—些自己不熟悉或不願意做的事，如智能家電、烹調等。
(5)新型計算機
目前新一代計算機正處在設想和研製階段。新一代計算機是把信息採集、存儲處理、通信和人工智慧結合在一起的計算機系統。
11．簡述計算學科的定義、計算學科的本質、計算學科的三個過程。
計算學科是對描述和變換信息的演算法過程，包括對理論分析、設計、效率、實現和應用等進行的系統研究。計算學科的研究包括了從演算法與可計算性的研究到根據可計算硬體和軟體的實際實現問題的研究。
計算學科的根本問題是「什麼能被有效地自動進行？」。計算學科的根本問題討論的是能行性的有關內容，而凡是與能行性有關的討論都是處理離散對象的。
計算學科的實質是學科方法論的思想，其關鍵問題是抽象、理論和設計三個過程相互作用的問題。
(1)理論
理論是數學科學的根本。應用數學家們都認為，科學的進展都是基於純數學的。應用數學用數學的方法推動經驗科學和工程學的發展，同時又不斷刺激對新數學的需要，為純理論數學提出新的問題。
(2)抽象
抽象(模型化)是自然科學的根本。科學家們相信，科學進展的過程基本上都是形成假設，然後用模型化過程去求證。
(3)設計
設計是工程的根本。工程師們認為，工程進展基本上都是提出問題，然後通過設計去構造系統，以解決問題。
12．簡述計算機科學與技術學科的定義。
計算機科學技術是研究計算機的設計與製造和利用計算機進行信息獲取、表示、存儲、處理、控制等的理論、原則、方法和技術的學科，包括科學與技術兩方面。科學側重於研究現象、揭示規律；技術則側重於研製計算機和研究使用計算機進行信息處理的方法與技術手段。科學是技術的依據，技術是科學的體現；技術得益於科學，它又向科學提出新的課題。
13．簡述計算機科學課程體系的核心內容。
計算學科課程體系的教學內容歸結為14個知識體，包括：
(1)離散結構(PS)
計算學科是以離散型變數為研究對象，離散數學對計算技術的發展起著十分重要的作用。隨著計算技術的迅猛發展，離散數學越來越受到重視。
(2)程序設計基礎(PF)
《計算作為一門學科》報告指出了程序設計在計算學科的正確地位：程序設計是計算學科課程中固定練習的一部分，是每一個計算學科專業的學生應具備的能力，是計算學科核心科目的一部分，程序設計語言還是獲得計算機重要特性的有力工具。
(3)演算法與復雜性(AL)
演算法是計算機科學和軟體工程的基礎，現實世界中，任何軟體系統的性能僅依賴於兩個基本點方面，一方面是所選擇的演算法；另一方面是各不同層次實現的適宜性和效率。
(4)組織與體系結構(AR)
計算機在計算中處於核心地位，如果沒有計算機，計算學科只是理論數學的一個分支，應該對計算機系統的功能構件、以及他們的特點/性能和相互作用有一定的理解。
(5)操作系統(OS)
操作系統定義了對硬體行為的抽象，程序員用它來對硬體進行控制。操作系統還管理計算機用戶間的資源共享。
(6)網路計算(NC)
計算機和通信網路的發展，尤其是基於TCP/IP的網路的發展使得網路技術在計算學科中更加重要。
(7)程序設計語言(PL)
程序設計語言是程序員與計算機交流的主要工具。一個程序員不僅要知道如何使用一種語言進行程序設計，還應理解不同語言的程序設計風格。
(8)人-機交互(HL)
人機交互重點在於理解人對互動式對象的交互行為，知道如何使用以人為中心的方法開發和評價交互軟體系統，以及人機交互設計問題的一般知識。
(9)圖形學和可視化計算(GV)
該主領域的主要內容包括：計算機圖形學、可視化、虛擬現實、計算機視覺等4 個學科子領域的研究內容。
(10)智能系統(IS)
人工智慧領域關心的問題是自主代理的設計和分析。智能系統必須干知其環境，合理地朝著指定的任務行動，並與其它代理和人進行交互。
(11)信息管理(IM)
信息系統幾乎在所有使用計算機的場合都發揮著重要的作用。
(12)軟體工程(SE)
軟體工程是關於如何有效地利用建立滿足用戶和客戶需求的軟體系統理論/知識和實踐的學科，可以應用於小型、中型、大型系統。
(13)數值計算科學(CN)
從計算學科的誕生之日起，科學計算的數值方法和技術就構成了計算機科學研究的一個主要領域。
(14)社會和職業問題(SP)
大學生需要懂得計算學科本身基本的文化、社會、法律和道德問題。還需要培養學生提出有關計算的社會影響這樣嚴肅問題以及對這些問題的可能答案進行評價的能力。學生還需要認識到軟硬體銷售商和用戶的基本法律權利，也應意識到這些權利的基本基礎——道德價值觀。

三．討論題
1．計算機的產生是世紀最偉大的成就之一，具體體現在哪些方面？根據你的觀察，請列出計算機的應用。
答案略。
2．計算機提供了無限的機會和挑戰。利用它可以更快更好地完成許多事情，可以方便地和全世界的人們聯系和通信。但是，是否想過事情的反面呢？所有的變化都是積極的么？計算機的廣泛使用會產生什麼負面的影響嗎？討論這些問題和其他所能想到的問題。
答案略。

是這個嗎?

『柒』 《編譯原理》pdf下載在線閱讀，求百度網盤雲資源

《編譯原理》（陳意雲）電子書網盤下載免費在線閱讀

鏈接：

書名：編譯原理

作者：陳意雲

豆瓣評分：6.2

出版社：高等教育出版社

出版年份：2003-1

頁數：381

內容簡介：

《編譯原理》介紹編譯器構造的一般原理和基本實現方法，主要內容包括詞法分析、語法分析、語義分析、中間代碼生成、代碼優化和目標代碼生成等。除了介紹命令式編程語言的編譯技術外，《編譯原理》還介紹面向對象語言和函數式編程語言的實現技術。《編譯原理》還強調一些相關的理論知識，如形式語言和自動機理論、語法制導的定義和屬性文法、類型論和類型系統等。

《編譯原理》取材廣泛新穎、圖文並茂，注意理論聯系實際。為滿足教師教學和學生自學及考研需求，《編譯原理》作者編寫了配套教學參考書《編譯原理習題精選與解析》（高等教育出版社2005年8月出版），同時提供本課程的電子教案，可從高等教育出版社高等理工教學資源網免費下載。《編譯原理》可作為高等學校計算機科學及相關專業的教材，也可供計算機軟體工程技術人員參考使用。

『捌』 形式語言與自動機理論

《形式語言與自動機》是關於理論計算機的，理論研究用的。從事計算機科學沒有理論知識是不行的。
《模糊數學》跟純資料庫沒有什麼直接關系，但是以後你做數據倉庫與知識挖掘的話會用到人工智慧和模糊數學的
感覺《隨即過程》和人工智慧和網路的關系比較大。《計算機體系結構》是計算機科學與技術專業必須要學的，以後凡是涉及到硬體結構與組織形式的課程都會用到它
順便問一句你很喜歡資料庫嗎？無論你以後做計算機的哪方面工作，都要對計算機有一個相對全面的了解，打好基礎，不要急功近利。一點小小建議