形式語言和自動(dòng)機(jī)

形式語言和自動(dòng)機(jī)

自動(dòng)機(jī)的概念在1936年首先由圖靈（A．M．Turing）提出，他設(shè)計(jì)的自動(dòng)機(jī)稱為圖靈機(jī)。

以后，丘奇（Church）提出了一個(gè)假設(shè)：圖靈機(jī)的計(jì)算能力代表著可實(shí)現(xiàn)的計(jì)算裝置的基本范圍?？梢宰C明，任何能在電子計(jì)算機(jī)上實(shí)現(xiàn)的計(jì)算都能用圖靈機(jī)進(jìn)行描述。

形式語言大約于1956年問世，N·喬姆斯基（NoamChomsky）給出一種文法的數(shù)學(xué)模型。到了1959年，喬姆斯基又將文法分為四類，即0型（無限止）文法、1型（上下文有關(guān)）文法、2型（上下文無關(guān)）文法和3型（正則）文法?，F(xiàn)在已可以證明，它們分別和圖靈機(jī)、不確定的線性界限自動(dòng)機(jī)、不確定的下推自動(dòng)機(jī)和有限自動(dòng)機(jī)等價(jià)。隨著計(jì)算機(jī)高級語言的發(fā)展，人們發(fā)現(xiàn)ALGOL語言可由上下文無關(guān)語言定義。因此，形式語言與編譯理論有著密切的聯(lián)系。此外，形式語言作為一個(gè)廣泛的數(shù)學(xué)模型，它描述了科學(xué)技術(shù)和各種工程中的變化過程。從此之后，研究工作相當(dāng)活躍，形式語言和自動(dòng)機(jī)理論相互滲透，緊密結(jié)合，使它成為計(jì)算機(jī)科學(xué)的一個(gè)重要分支。

這些理論在編譯程序理論、人工智能、可計(jì)算性和時(shí)序電路設(shè)計(jì)等領(lǐng)域中有著廣泛的應(yīng)用。

第九章糾錯(cuò)碼初步

糾錯(cuò)編碼技術(shù)是五十年代提出，六十年代發(fā)展起來的。近來，由于數(shù)字通訊，特別是衛(wèi)星通訊的發(fā)展，以及在數(shù)字計(jì)算機(jī)和數(shù)據(jù)處理等新興科學(xué)技術(shù)中廣泛應(yīng)用，給糾錯(cuò)碼開拓了新的發(fā)展前景。9-1通訊模型和糾錯(cuò)的基本概念

通訊方法：寫一封信，通一次，發(fā)一份電報(bào)，通過廣播等多種手段。

一般通訊手段都要經(jīng)過三個(gè)必要步驟：

1．在發(fā)送端將所要傳送的信息轉(zhuǎn)換成電信號(hào)。

2．通過可靠的信道，傳輸電信號(hào)。

3．在接收端將接收到的電信號(hào)還原成原來的信息。

電信號(hào)可分為模擬信號(hào)和數(shù)字信號(hào)兩種。例如機(jī)話筒輸出的電壓，其幅值隨說話人的語有連續(xù)變化，它與信息直接對應(yīng)，且可取無限多個(gè)值，這種信號(hào)稱為模擬信號(hào)。又如電報(bào)，是以四個(gè)數(shù)字代表一個(gè)漢字，且代表每個(gè)數(shù)字的脈沖信號(hào)，其高度只取兩個(gè)值分別表示空號(hào)和傳號(hào)，（通常用0