形式語言與自動機理論

內(nèi)容概要

　　形式語言與自動機理論是計算機科學與技術專業(yè)的一門重要課程。本書是作者結合其20余年來在大學講授該門課程的經(jīng)驗和體會，選擇和組織有關內(nèi)容撰寫而成。不僅含有有關正則語言、上下文無關語言的文法、識別模型及其性質、圖靈機的基本知識，更涉及到本學科方法論中所包含的3個學科形態(tài)。其內(nèi)容特點是抽象和形式化，既有嚴格的理論證明，又具有很強的構造性，從而培養(yǎng)學生的形式化描述和抽象思維能力，使學生了解和初步掌握“問題、形式化、自動化(計算機化)”的解題思路。為了便于學生對內(nèi)容的掌握，附錄A還給出了建議的教學設計。　　　
　　本書配套出版有《形式語言與自動機理論教學參考書(第2版)》，歸納各章知識點，解讀主要內(nèi)容，解析典型習題?！　　?br />　　本書適合作為計算機科學與技術專業(yè)的高年級本科生、研究生的教材，也可供相關專業(yè)的學生、教師和科研人員參考。

作者簡介

蔣宗禮，1978年3月至1984年7月在哈爾濱工業(yè)大學計算機學科學習，先后到美國、加拿大進修，在哈爾濱工業(yè)大學和北京工業(yè)大學主講編譯原理、形式語言與自動機理論、人工神經(jīng)網(wǎng)絡等課程。國家級教學名師，國家級教學團隊負責人，國家精品課程負責人，主編有國家級精品教材，獲國家教學成果二等獎2項，另有十余項省部級教學、科研成果一、二、三等獎。曾獲中國高校優(yōu)秀青年學者、寶鋼優(yōu)秀教師、航天部優(yōu)秀青年教師等榮譽稱號。主要學術兼職有中國工程教育認證協(xié)會籌備委員會學術委員會委員、中國工程教育認證協(xié)會籌備委員會2012-2013年度結論審議委員會委員、全國工程教育專業(yè)認證專家委員會計算機類專業(yè)認證分委員會成員、教育部高等學校計算機科學與技術專業(yè)教學指導分委員會秘書長、全國高校計算機教育研究會理事長、中國計算機學會教育專業(yè)委員會副主任。

書籍目錄

第1章 緒論
1.1 集合的基礎知識
1.1.1 集合及其表示
1.1.2 集合之間的關系
1.1.3 集合的運算
1.2 關系
1.2.1 二元關系
1.2.2 等價關系與等價類
1.2.3 關系的合成
1.2.4 遞歸定義與歸納證明
1.2.5 關系的閉包
1.3 圖19
1.3.1 無向圖
1.3.2 有向圖
1.3.3 樹
1.4 語言
1.4.1 什么是語言
1.4.2 形式語言與自動機理論的產(chǎn)生與作用
1.4.3 基本概念
1.5 小結
習題
第2章 文法
2.1 啟示
2.2 形式定義
2.3 文法的構造
2.4 文法的喬姆斯基體系
2.5 空語句
2.6 小結
習題82
第3章 有窮狀態(tài)自動機
3.1 語言的識別
3.2 有窮狀態(tài)自動機
3.3 不確定的有窮狀態(tài)自動機
3.3.1 作為對DFA的修改
3.3.2 NFA的形式定義
3.3.3 NFA與DFA等價
3.4 帶空移動的有窮狀態(tài)自動機
3.5 FA是正則語言的識別器
3.5.1 FA與右線性文法
3.5.2 FA與左線性文法
3.6 FA的一些變形
3.6.1 雙向有窮狀態(tài)自動機
3.6.2 帶輸出的FA
3.7 小結
習題
第4章 正則表達式
4.1 啟示
4.2 正則表達式的形式定義
4.3 正則表達式與FA等價
4.3.1 正則表達式到FA的等價變換
4.3.2 正則語言可以用正則表達式表示
4.4 正則語言等價模型的總結
4.5 小結
習題153
第5章 正則語言的性質
5.1 正則語言的泵引理
……
第6章 上下文無關語言
第7章 下推自動機
第8章 上下文無關語言的性質
第9章 圖靈機
第10章 上下文有關語言
附錄A 教學設計
附錄B 縮寫符號
詞匯索引
參考文獻

章節(jié)摘錄

版權頁：   插圖：   9.2.4 多維圖靈機 前面介紹過的圖靈機的帶都是一維的。也就是說，那些圖靈機的輸入帶要么是只可以向右無限延長的，要么是只可以向左和向右延長的，因而讀頭只能向前或者向后移動?，F(xiàn)在將圖靈機的帶定義成多維的。這種圖靈機的讀頭可以沿著多個維移動，稱這種圖靈機為多維圖靈機（multi-dimensional Turing machine）。如果一個圖靈機可以沿著k維移動，則稱之為k維圖靈機（k-dimensional Turing machine）。k維圖靈機的帶由志維陣列組成，而且在所有的2k個方向上都是無窮的，它的讀頭可以向著2k個方向中的任一個移動。對前面曾經(jīng)討論過的雙向無窮帶圖靈機來說，雖然它的帶在左、右兩個方向上都是無窮，但是，在圖靈機的運行期間的任意時刻，只有有限長度的帶上含有非空白的內(nèi)容。與此相同，在任意時刻，一個k維圖靈機的每一維上也只有有限多個道各自含有有窮多個非空白字符。這就是說，這些非空白的內(nèi)容可以被一個有限的k維立方體所包含。這使得我們可以將這k個維上的有窮長度的字符串用適當?shù)姆绞浇M合成可以在一維帶上存放的字符串。這種做法與我們在計算機中存放多維數(shù)組的做法一樣。 為了說明具體的做法，下面討論二維圖靈機如何被一維圖靈機模擬。只要找到了相應的模擬方法，按照“遞歸定義”、“遞歸求解”的思路，很容易得到志維圖靈機到一維圖靈機的轉換方法。 設M是一個二維圖靈機，按照“行優(yōu)先”的方式用一維帶來存放它的內(nèi)容。圖9-10是M在某一時刻帶上的所有非空白字符的存儲情況，可以用一個符串表示這一內(nèi)容。它正好對應于一維帶的表示。我們約定，每行的內(nèi)容之間用一個特殊的帶符號#相隔。稱一行的內(nèi)容為一段（segment），并且將#稱為段分割符?！橛米髟撟址拈_始標志，＄用作該字符串的結束標志。這樣，圖9-10所示的帶內(nèi)容可以用如下字符串表示： ￠Ba1a1a3a4BBBBBB#Ba5Ba6a7a8a9a10 BBB#Ba11 BBBBa12 Ba13 Ba14#a15a16 BBBBBBBBa16 # BBBa17 BBBBBa18 B#a19a20 BBBBBBBBB#BBBBBBBBBBa21＄ 現(xiàn)在來具體考慮一維圖靈機M′如何實現(xiàn)對二維圖靈機M的移動的模擬。

編輯推薦

《普通高等教育"十一五"國家級規(guī)劃教材?21世紀大學本科計算機專業(yè)系列教材:形式語言與自動機理論(第2版)》強調(diào)能力培養(yǎng)，以知識為載體，注重模型建立、構造、變換、證明的方法與思想探討，引導讀者挖掘知識背后的內(nèi)容，強化專業(yè)基本能力和創(chuàng)新能力的培養(yǎng)。取材合適，結構嚴謹，深入淺出，把握知識點間的聯(lián)系，安排鋪墊，分散難點，突出重點，努力化解深奧，保持基本內(nèi)容抽象和形式化，通過思路表達的可視化提高了易懂性，富有啟發(fā)性，使抽象、枯燥的內(nèi)容變得吸引人。《普通高等教育"十一五"國家級規(guī)劃教材?21世紀大學本科計算機專業(yè)系列教材:形式語言與自動機理論(第2版)》適合作為計算機科學與技術專業(yè)的高年級本科生、研究生的教材，也可供相關專業(yè)的學生、教師和科研人員參考。

圖書封面

圖書標簽Tags

無

評論、評分、閱讀與下載

---

    形式語言與自動機理論 PDF格式下載

---