形式語言

在數學、邏輯和電腦科學中，形式語言（英語：Formal language）是用精確的數學或機器可處理的公式定義的語言。

如語言學中語言一樣，形式語言一般有兩個方面：語法和語意。專門研究語言的語法的數學和電腦科學分支叫做形式語言理論，它只研究語言的語法而不致力於它的語意。在形式語言理論中，形式語言是一個字母表上的某些有限長字串的集合。一個形式語言可以包含無限多個字串。

語言的形式定義

字母表與字串

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

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

語言

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

對於任意一個字母表，記全體長度為 n 的子串為 $\Sigma ^{n}$ ，特別的，規定 $\Sigma ^{0}$ 為{ε}，則還可以定義

$\Sigma ^ {*} = \Sigma ^{0}\cup \Sigma ^{1}\cup \cdots \cup \Sigma ^{n}\cup \cdots$

$\Sigma ^{*}$ 包含了字母表 $\Sigma$ 所能構成的所有字串。語言（一般記為 L ）定義為 $\Sigma ^{*}$ 的任意子集。

下面給出一些語言的例子， $\{hello , world\}$ 是一個包含兩個字串的集合，也可以被視為小寫字母構成的字母表上的一個語言。而實際上研究的語言的例子則常常更為複雜，例如所有合法的C語言程式串構成的集合也可以視作ASCII上的一個語言（假定編譯器只支援英文符號）。

需要注意的一點是， $\Sigma ^{*}$ 的空子集 ∅ 與只包含空字串的語言 {ε} 是兩個不同的語言。

語言間的運算

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

字串集合的交集、聯集、差集等運算。
連接運算：L₁L₂ = { xy | x 屬於L₁並且 y 屬於L₂ }。
冪運算：Lⁿ = L … L （共 n 個 L 連接在一起），L⁰ = {ε}。
閉包運算：L^* = L⁰∪L¹∪…∪Lⁿ∪…。
右商運算：L₁/L₂ = {x | 存在 y 屬於L₂使得 xy 屬於L₁}。
設 S ⊆ Σ^* 是一個語言，S 的補語言定義為集合 {ω | ω ∈ Σ^* 且 ω ∉ S}

語言的表示方法

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

列舉法

如果一個形式語言的元質數目是有限的，那麼可以通過列舉它的各個字串來嚴格地定義它。

形式文法

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

正規表示式

正規表示式是一種很多程式語言和庫都支援的語法，這種語法可以用於匹配符合一定條件的字串，經常用於文字的搜尋和過濾。從名稱上來說，正規表示式應當是對應於正規語言的，在形式語言領域內所稱的正規表示式確實如此。不過，在實際的程式語言中，很多正規表示式已經通過引入複雜的擴充，可以匹配正規表示式所不能描述的內容。形式語言中的正規表示式和一般程式語言中所稱的正規表示式在語法上也有較大差異。

自動機

直覺上來說，自動機消耗輸入符號，並在自身的不同狀態間轉移，可以通過狀態機消耗完整個字串之後是否達到某些特定狀態來定義一個字串是否屬於某一個語言。語言可以通過某種自動機來辨識，比如圖靈機、有限狀態自動機。

參考文獻

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.

參見

外部連結

喬姆斯基層級	文法	語言	極小自動機
類型 0	無限制	遞迴可列舉	圖靈機
—	(無公用名)	可判定	判定器
類型 1	上下文有關	上下文有關	線性有界
—	附標	附標	巢狀堆疊
—	Linear context-free rewriting systems etc.	上下文有關文法	Thread automata
—	樹-鄰接	適度上下文有關	嵌入下推
類型 2	上下文無關	上下文無關	非確定下推
—	確定上下文無關	確定上下文無關	確定下推
—	Visibly pushdown	Visibly pushdown	Visibly pushdown
類型 3	正則	正則	有限
—	—	Star-free	Counter-free (with aperiodic finite monoid)