亚洲国产区中文,国产精品91高清,亚洲精品中文字幕久久久久,亚洲欧美另类久久久精品能播放

語言的形式定義

字母表與字符串

語言定義在某一個特定的 字母表 上，字母表（經(jīng)常記作 Σ ）可以為任意有限集合。例如集合 { a , b , c . . . , z } {\displaystyle \{a,b,c...,z\}} 就表示所有小寫字母構(gòu)成的字母表。

字符串 是字母表中的元素構(gòu)成的有窮序列，以之前定義的小寫字母表為例，“hello”，“wikipedia”,“abcjkg”都是上面的串，而“AbCd”就不是上面的串了。記號 ε 表示空串——它是一個特殊的長度為0的串。

語言

直覺上，一個語言是字母表所能構(gòu)成的所有串的集合的一個子集，具體來說：

對于任意一個字母表，記全體長度為 n 的子串為 Σ Σ --> n {\displaystyle \Sigma ^{n}} ，特別的，規(guī)定 Σ Σ --> 0 {\displaystyle \Sigma ^{0}} 為{ε}，則還可以定義

Σ Σ --> ? ? --> = Σ Σ --> 0 ∪ ∪ --> Σ Σ --> 1 ∪ ∪ --> ? ? --> ∪ ∪ --> Σ Σ --> n ∪ ∪ --> ? ? --> {\displaystyle \Sigma ^{*}=\Sigma ^{0}\cup \Sigma ^{1}\cup \cdots \cup \Sigma ^{n}\cup \cdots }

Σ Σ --> ? ? --> {\displaystyle \Sigma ^{*}} 包含了字母表 Σ Σ --> {\displaystyle \Sigma } 所能構(gòu)成的所有字符串。 語言 （一般記為 L ）定義為 Σ Σ --> ? ? --> {\displaystyle \Sigma ^{*}} 的任意子集。

下面給出一些語言的例子， { h e l l o , w o r l d } {\displaystyle \{hello,world\}} 是一個包含兩個字符串的集合，也可以被視為小寫字母構(gòu)成的字母表上的一個語言。而實際上研究的語言的例子則常常更為復(fù)雜，例如所有合法的C語言程序串構(gòu)成的集合也可以視作ASCII上的一個語言（假定編譯器只支持英文符號）。

需要注意的一點是， Σ Σ --> ? ? --> {\displaystyle \Sigma ^{*}} 的空子集? 與只包含空串的語言 {ε} 是兩個不同的語言。

語言間的運算

語言間的運算就是 Σ 冪集上的運算。

字符串集合的交并補等運算。

連接運算：L 1 L 2 = { xy | x 屬于L 1 并且 y 屬于L 2 }。

冪運算：L = L … L （共 n 個 L 連接在一起），L = {ε}。

閉包運算：L = L ∪L ∪…∪L ∪…。

右商運算：L 1 /L 2 = {x | 存在 y 屬于L 2 使得 xy 屬于L 1 }。

設(shè) S ? Σ 是一個語言， S 的補語言定義為集合 {ω | ω ∈ Σ 且 ω ? S }

語言的表示方法

不像自然語言，一個形式語言作為一個集合，需要有某種明確的標(biāo)準(zhǔn)來定義一個字符串是否是它的元素。這可以通過多種方法來完成，下面將給出一些例子：

枚舉法

如果一個形式語言的元素數(shù)目是有限的，那么可以通過枚舉它的各個字串來嚴(yán)格地定義它。

形式文法

通過形式文法來產(chǎn)生（參見喬姆斯基譜系）。

正則表達(dá)式

正則表達(dá)式是一種很多編程語言和庫都支持的語法，這種語法可以用于匹配符合一定條件的字符串，經(jīng)常用于文本的搜索和過濾。從名稱上來說，正則表達(dá)式應(yīng)當(dāng)是對應(yīng)于正則語言的，在形式語言領(lǐng)域內(nèi)所稱的正則表達(dá)式確實如此。不過，在實際的編程語言中，很多正則表達(dá)式已經(jīng)通過引入復(fù)雜的擴展，可以匹配正則表達(dá)式所不能描述的內(nèi)容。形式語言中的正則表達(dá)式和一般編程語言中所稱的正則表達(dá)式在語法上也有較大差異。

自動機

直覺上來說，自動機消耗輸入符號，并在自身的不同狀態(tài)間轉(zhuǎn)移，可以通過狀態(tài)機消耗完整個字符串之后是否達(dá)到某些特定狀態(tài)來定義一個字符串是否屬于某一個語言。語言可以通過某種自動機來識別，比如圖靈機、有限狀態(tài)自動機。

參考文獻(xiàn)

Hamilton, A. G. Logic for Mathematicians. Cambridge University Press. 1978. ISBN 0-521-21838-1.

Ginsburg, Seymour. Algebraic and automata theoretic properties of formal languages. North-Holland. 1975. ISBN 0-7204-2506-9.

Harrison, Michael A. Introduction to Formal Language Theory. Addison-Wesley. 1978.

Hopcroft, John E.; Jeffrey D. Ullman. Introduction to Automata Theory, Languages, and Computation. Reading, Massachusetts: Addison-Wesley Publishing. 1979. ISBN 0-201-02988-X.

Rozenberg, Grzegorz; Arto Salomaa. Handbook of Formal Languages: Volume I-III. Springer. 1997. ISBN 3-540-61486-9.

Suppes, Patrick. Introduction to Logic. D. Van Nostrand. 1957. ISBN 0-442-08072-7.

參見

形式文法

形式方法

形式科學(xué)

形式系統(tǒng)

數(shù)學(xué)符號

編程語言

本體語言

免責(zé)聲明：以上內(nèi)容版權(quán)歸原作者所有，如有侵犯您的原創(chuàng)版權(quán)請告知，我們將盡快刪除相關(guān)內(nèi)容。感謝每一位辛勤著寫的作者，感謝每一位的分享。