形式語言

形式語言的字母是從該語言的字符串可以形成的一組符號，字母，或標記，;通常它的要求是有限的。

字符串由這個稱為字的字母形成，這些詞屬於一個特定的形式語言有時被稱為形式公式。一個正式的語言，往往是通過一個正式的語法，如正則文法或上下文無關文法定義，稱作形成規律。

形式語言理論主要研究的是內部結構模式這類語言的純粹的語法領域。形式語言理論是從語言學衍生而來，作為一種理解自然語言的句法規律。在計算機科學中，形式語言通常作為定義編程語言和語法的基礎，是正式版本的自然語言的子集。在計算複雜性理論中，決策問題通常定義為形式語言，複雜類被定義為形式語言的集合，它能被具有有限計算能力的機器所解析。在邏輯和數學基礎中，形式語言是用來表示公理系統的語法。

自然語言（Natural Language）就是人類講的語言，比如漢語、英語和法語。這類語言不是人為設計（雖然有人試圖強加一些規則）而是自然進化的。形式語言（Formal Language）是為了特定應用而人為設計的語言。例如數學家用的數字和運算符號、化學家用的分子式等。編程語言也是一種形式語言，是專門設計用來表達計算過程的形式語言。 ^[1] 

形式語言有嚴格的語法（Syntax）規則，例如，3+3=6是一個語法正確的數學等式，而3=+6$則不是，H2O是一個正確的分子式，而2Zz則不是。語法規則是由關於符號（Token）和結構（Structure）的規則所組成的。Token的概念相當於自然語言中的單詞和標點、數學式中的數和運算符、化學分子式中的元素名和數字。關於Token的規則稱為詞法（Lexical）規則，而關於語句結構的規則稱為語法（Grammar）規則。 ^[1] 

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

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

連接運算：L1L2={xy|x屬於L1並且y屬於L2}。

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

閉包運算：L*=L0∪L1∪…∪Ln∪…。

右商運算：L1/L2={x|存在y屬於L2使得xy屬於L1}。

設S⊆Σ*是一個語言，S的補語言定義為集合{ω|ω∈Σ*且ω∉S}

一個形式語言可以通過多種方法來限定自身，比如：

枚舉出各個字串（只適用於有限字串集合）。

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

通過正則表達式來產生。

通過某種自動機來識別，比如圖靈機、有限狀態自動機。

編程語言

主要文章：語法（編程語言和編譯器）

編譯器通常有兩個不同的部分組成。一個詞法分析器，由一個像lex的工具形成。那識別編程語言的語法標記。例如：標識符或關鍵字，在一個簡單的語言表達形式中，通常是正則表達式工具。在最基本的概念，一個解析器由一個類似yacc的解析生成器構成。試圖判斷源程序是否有效。當然，編譯器做的不僅僅是解析源代碼，他們通常把它翻譯成一些可執行格式。因此，一個解析器通常輸出多是或否的回答，一個典型的抽象語法樹，這是由編譯器後續階段用於最終生成機器代碼，包含直接運行在硬件執行，或一些中間代碼需要虛擬機執行。

也稱代數語言學,它研究一般的抽象符號系統,運用形式模型對語言(包括人工語言和自然語言)進行理論上的分析和描寫.

形式文法:是一種格式,用來説明什麼句子在該語言中是合法的,並指明把詞組合成短語和句子的規則.

描述語言有三種途徑:1,窮舉2,文法 3,自動機 其中文法是指的產生過程,而自動機是指的識別過程.一種語言,如果存在對它的識別過程,就一定存在對它的產生過程,反之亦然.

現行的形式語法系統是Chomsky於1959年為了描述自然語言而提出的一種理論模型

如何嚴格的定義形式化的語言

形式文法:一個形式文法G由四個部分組成,可記作G={VN, VT, S , P },其中:

VN:稱為文法G的非終結符號字母表,VN不出現在G所表示的語言集合的句子中;

VT:稱為文法G的終結符號字母表,G所表示的語言的句子由VT中的元素組成,VN ∩VT = ;S :代表句子符號,S∈VN .

P :代表一組式子組成的集合,P 中的式子具有如下形式:α->β

產生式需要滿足下面的條件:1)α可以是VN 和VT 上的任意字符串,但其中必須至少包含一個非終結符,並且不能是空字符;2)β可以是VN 和VT 上的任意字符串,也可以是空字符;3)P 中至少有一個產生式中的α得由S 來充當;

形式語言的特點

1,高度的抽象化(採用形式化的手段-專用符號,數學公式-來描述語言的結構關係,這種結構關係是抽象的)2,是一套演繹系統(形式語言本身的目的就是要用有限的規則來推導語言中無限的句子,提出形式語言的哲學基礎也是想用演繹的方法來研究自然語言)3,具有算法的特點.(比如説句法分析中採用不同的算法來構造句子的句法推導樹)

喬姆斯基把文法分成4種類型，即0型，1型，2型，和3型。0型文法也稱短語文法，0型文法的能力相當於圖靈機（Turing），或者説任何0型語言都是遞歸可枚舉的。1型文法也稱上下文有關法，其能力相當於線性界限自動機。2型文法也稱上下文無關法，其能力相當於非確定的下推自動機。3型文法也稱右線性文法，由於這種文法等價於正規式，所以也稱正規文法。從文法描述語言的能力來説，0型文法最強，3型文法最弱。