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

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

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