100年第2學期-0938 自動機與形式語言 課程資訊

評分方式

評分項目	配分比例	說明
作業與報告	30
小考	30
期中考	20
期末考	20

教育目標

形式語言與自動機理論是電腦科學理論的重要基礎。本課程主要介紹Chomsky文法體系的四類文 法以及它們與有限自動機、下推自動機、線性界限自動機和圖靈機之間的關係。此外，對語言 的各種運算和封閉性質、判定問題及不可判定性以及確定的上下文無關語言與LR-文法也進行了 討論。課程中還介紹了一些文法和自動機在文件編輯、編譯器設計、程式語言以及邏輯電路和 時序電路設計中的應用。

課程概述

本課程主要介紹Chomsky文法體系的四類文法以及它們與有限自動機、下推自動機、線性界限自動機和圖靈機之間的關係。此外，對語言的各種運算和封閉性質、判定問題及不可判定性以及確定的上下文無關語言與LR-文法也進行了討論。課程中還介紹了一些文法和自動機在文件編輯、編譯器設計、程式語言以及邏輯電路和時序電路設計中的應用。

基本資料

選修課，學分數：0-3
上課時間：二/9[C215] 三/8,9[C219]
修課班級：資工系3,4
修課年級：年級以上
選課備註：

參考書目

1. An Introduction to Formal Languages and Automata, Fourth Edition, Linz.
2. Introduction to the Theory of Computation, Michael Sipser.
3. Computability, Complexity, and Languages, Davis and Weyuker.
4. Formal Languages and Their Relation to Automata, Hopcroft and Ullman.
5. Introduction to Computer theory, Cohen, John Wiley & Sons.
6. Theoretical Foundations of Computer Science, Mandrioli and Ghezzl, John Wiley & Sons.
7. 形式語言與運算理論入門，張世敏 譯，文魁圖書。