形式語言與自動(dòng)機(jī)理論若干問題研究.pdf

1、計(jì)算理論是研究使用計(jì)算機(jī)解決計(jì)算問題的數(shù)學(xué)理論。有三個(gè)核心領(lǐng)域：形式語言與自動(dòng)機(jī)理論、可計(jì)算性理論和計(jì)算的復(fù)雜性理論?？捎?jì)算性理論的中心問題是建立計(jì)算的數(shù)學(xué)模型，進(jìn)而研究哪些是可計(jì)算的，哪些是不可計(jì)算的。計(jì)算的復(fù)雜性理論研究算法的時(shí)間復(fù)雜性和空間復(fù)雜性。在可計(jì)算性理論中，將問題分成可計(jì)算的和不可計(jì)算的；在復(fù)雜性理論中，目標(biāo)是把可計(jì)算的問題分成簡單的和復(fù)雜的。
　　 形式語言與自動(dòng)機(jī)理論論述計(jì)算的數(shù)學(xué)模型的定義和性質(zhì)，這些模型在計(jì)

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