形式語言與自動機理論若干問題研究.pdf

1、計算理論是研究使用計算機解決計算問題的數(shù)學理論。有三個核心領(lǐng)域：形式語言與自動機理論、可計算性理論和計算的復雜性理論?？捎嬎阈岳碚摰闹行膯栴}是建立計算的數(shù)學模型，進而研究哪些是可計算的，哪些是不可計算的。計算的復雜性理論研究算法的時間復雜性和空間復雜性。在可計算性理論中，將問題分成可計算的和不可計算的；在復雜性理論中，目標是把可計算的問題分成簡單的和復雜的。
　　 形式語言與自動機理論論述計算的數(shù)學模型的定義和性質(zhì)，這些模型在計

2、算機科學的若干應用領(lǐng)域中起著重要作用，其應用范圍已被擴展到生物工程、自動控制系統(tǒng)、圖像處理與模式別等許多領(lǐng)域。
　　 本文主要研究形式語言與自動機理論中的形式語言理論、自動機理論和形式語言與自動機之間等價性理論的若干問題。研究內(nèi)容包括：
　　 (1)形式語言與自動機理論中關(guān)于空串ε的一些問題。
　　 (2)四類語言對聯(lián)合、連接、克林閉包運算的有效封閉性問題。
　　 (3)根據(jù)等價類構(gòu)造一類有限狀態(tài)自動機的