基本介紹
詳細內容,自然語言和形式語言,語言間的運算,語言的表示方法,套用,形式語言學,
詳細內容
形式語言的字母是從該語言的字元串可以形成的一組符號，字母，或標記，;通常它的要求是有限的。
字元串由這個稱為字的字母形成，這些詞屬於一個特定的形式語言有時被稱為形式公式。一個正式的語言，往往是通過一個正式的語法，如正則文法或上下文無關文法定義，稱作形成規律。
形式語言理論主要研究的是內部結構模式這類語言的純粹的語法領域。形式語言理論是從語言學衍生而來，作為一種理解自然語言的句法規律。在計算機科學中，形式語言通常作為定義程式語言和語法的基礎，是正式版本的自然語言的子集。在計算複雜性理論中，決策問題通常定義為形式語言，複雜類被定義為形式語言的集合，它能被具有有限計算能力的機器所解析。在邏輯和數學基礎中，形式語言是用來表示公理系統的語法。
自然語言和形式語言
自然語言（Natural Language）就是人類講的語言，比如漢語、英語和法語。這類語言不是人為設計（雖然有人試圖強加一些規則）而是自然進化的。形式語言（Formal Language）是為了特定套用而人為設計的語言。例如數學家用的數字和運算符號、化學家用的分子式等。程式語言也是一種形式語言，是專門設計用來表達計算過程的形式語言。
形式語言有嚴格的語法（Syntax）規則，例如，3+3=6是一個語法正確的數學等式，而3=+6$則不是，H2O是一個正確的分子式，而2Zz則不是。語法規則是由關於符號（Token）和結構（Structure）的規則所組成的。Token的概念相當於自然語言中的單詞和標點、數學式中的數和運算符、化學分子式中的元素名和數字。關於Token的規則稱為詞法（Lexical）規則，而關於語句結構的規則稱為語法（Grammar）規則。
語言間的運算
語言間的運算就是Σ*冪集上的運算。
連線運算：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,自動機 其中文法是指的產生過程,而自動機是指的識別過程.一種語言,如果存在對它的識別過程,就一定存在對它的產生過程,反之亦然.
如何嚴格的定義形式化的語言
形式文法:一個形式文法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 來充當;
形式語言的特點
