国产91青青成人a在线/在线视频成人/aaa成人永久在线观看视频/深夜草莓视频app

    《形式語言與自動機（第2版）/普通高等教育“十二五”規劃教材》扼要地介紹了形式語言與自動機的基本體系，是學習計算機科學基礎的教材和參考書。書中主要介紹了形式語言的基本概念、自動機模型以及形式語言與自動機的等價性，包括右線性文法與有限自動機、上下文無關文法與下推自動機、圖靈機以及無限制文法等。同時也介紹了形式語言與自動機的主要理論成果和應用實例。
　　《形式語言與自動機（第2版）/普通高等教育“十二五”規劃教材》不追求過多形式化討論，強調基本概念的直觀背景和主要定理證明的思路分析。書中配有較多的例題和習題，可作為工科計算機專業本科生的教材和研究人員的參考書。

本書扼要地介紹了形式語言與自動機的基本體系，是學習計算機科學基礎的教材和參考書。書中主要介紹形式語言的基本概念、自動機模型以及形式語言與自動機的等價性，包括右線性文法與有限自動機、上下文無關文法與下推自動機、圖靈機以及無限制文法等。同時介紹形式語言與自動機方面的主要理論成果和應用實例。本教材不追求過多形式化討論，強調基本概念的直觀背景和主要定理證明的思路分析，書中配有較多的例題和習題，適合作為工科計算機專業本科生的教材。

楊娟,女，北京郵電大學副教授。自1998年留校任教以來，一直教授北郵計算機學院本科生《形式語言與自動機》和《離散數學》兩門專業基礎課程，教學工作量飽滿，教學效果良好。曾獲校教學觀摩評比一等獎，校“燭光獎”候選人提名。

目    錄


第1章  基礎知識1


  1.1  集合與關系1


  1.2  邏輯6


  1.3  圖8


  1.4  證明技術14


    1.4.1  演繹證明15


    1.4.2  反證法16


    1.4.3  歸納定義與歸納法16


  1.5  典型例題解析18


  習題22


第2章  語言及文法26


  2.1  語言的定義與運算26


  2.2  文法28


  2.3  文法的分類30


  2.4  典型例題解析35


  習題36


第3章  有限自動機和右線性文法38


  3.1  有限自動機38


    3.1.1  有限狀態系統和有限自動機的概念38


    3.1.2  有限自動機的形式定義40


    3.1.3  設計有限自動機42


  3.2  不確定的有限自動機44


  3.3  DFA與NFA的等效46


  3.4  有ε轉換的不確定的有限自動機50


  3.5  正則集與正則式55


  3.6  右線性文法和正則集57


  3.7  正則表達式和有限自動機59


  3.8  右線性語言與有限自動機63


  3.９  右線性語言的性質67


    3.９.１  確定的有限自動機的化簡67


    3.９.２  泵浦引理70


    ３．９．３  右線性語言的封閉性72


    3.９.４  判定問題77


  3.１０  雙向和有輸出的有限自動機78


    3.１０.１  雙向有限自動機78


    3.１０.２  有輸出的有限自動機79


  3.11  正則表達式和有限自動機的應用82


    3.11.1  UNIX中的正則表達式82


    3.11.2  文本編輯程序83


    3.11.3  詞法分析83


    3.11.4  文本搜索與字符串匹配84


    3.11.5  單詞拼寫檢查85


  3.12  典型例題解析85


  習題90


形式語言與自動機(第2版)
目    錄
第４章  上下文無關文法與下推自動機94


  ４.１  推導樹與二義性94


  ４.２  上下文無關文法的變換99


  ４.3  Ｃｈoｍｓｋｙ范式和Ｇｒｅｉｂａｃｈ范式109


  ４.４  下推自動機112


  ４.５  上下文無關文法與下推自動機119


  4.6  上下文無關語言的性質125


    4.6.1  上下文無關語言的泵浦引理125


    4.6.2  上下文無關語言的封閉性127


    ４.6.3  上下文無關語言的判定問題129


    ４.6.４  上下文無關語言的二義性129


  ４.７  受限型上下文無關文法130


  4.8  上下文無關文法的應用131


    4.8.1  上下文無關文法在語法分析中的應用132


    4.8.2  上下文無關文法變換的應用133


    4.8.3  上下文無關文法的其他應用135


  4.9  典型例題解析135


  習題138


第5章  圖靈機142


  5.１  基本圖靈機142


  5.２  圖靈機的構造技術147


    5.２.１  控制器的存儲147


    5.２.２  多道機148


    5.２.3  核對符149


    5.２.４  移位151


    5.２.5  子程序151


  5.3  修改型圖靈機154


    5.3.１  雙向無限帶圖靈機154


    5.3.２  多帶圖靈機156


    5.3.3  不確定的圖靈機158


    5.3.４  二維圖靈機158


  5.４  圖靈機與無限制文法160


  5.5  線性有界自動機與上下文有關文法162


  5.6  典型例題解析162


  習題166


第6章  翻譯168


  6.１  翻譯式168


  6.２  轉換器172


    6.2.1  有限轉換器173


    6.2.2  下推轉換器175


  6.3  詞法分析180


  6.４  句法分析184


    6.4.1  自上而下解析185


    6.4.2  自下而上解析188


  習題191


第7章  自動機理論在通信領域的應用193


  7.1  狀態機基本模型及其局限性193


  7.2  MSC和SDL簡介195


  7.3  應用狀態機模型描述協議200


附錄  計算復雜性與可計算性基礎202


參考文獻210