兩級文法

兩級文法是下列兩種形式結構之一：

兩級形式語言的形式文法，這種語言是按兩個級別來指定的形式語言，比如，字和句兩個級別。用來生成其他形式文法的形式文法[1]。定義次級文法的規則的上下文無關文法可以生成導出文法的規則的一個有效的無限集合。可以生成另一個上下文無關文法的兩級文法比單一層上下文無關文法更加強力，因為有生成力的兩級文法已經實際上被證實是圖靈完全的。

基本介紹

• 中文名：兩級文法
• 學科：計算機

例子

眾所周知的非上下文無關語言是

這個語言的的兩級文法是元文法

• N::= 1 | N1
• X::= a | b

以及文法模式

Start::=

::=

::= X

形式文法

在計算機科學中，形式語言是：某個字母表上，一些有限長字串的集合，而形式文法是描述這個集合的一種方法。形式文法之所以這樣命名，是因為它與人類自然語言中的文法相似的緣故。

形式文法描述形式語言的基本想法是，從一個特殊的初始符號出發，不斷的套用一些產生式規則，從而生成出一個字串的集合。產生式規則指定了某些符號組合如何被另外一些符號組合替換。舉例來說，假設字母表只包含'a'和'b'兩個字元，初始符號是'S'，我們套用下述規則：

• 1. S -> aSb
• 2. S -> ba

於是我們可以通過把"S"重寫為"aSb"（規則1），我們還可以繼續套用這條規則把"aSb"重寫為"aaSbb"。這個重寫的過程不斷重複，直到結果中只包含字母表中的字母為止。在例子中，我們可以得到S -> aSb -> aaSbb -> aababb這樣的結果。由文法刻畫的語言，包含了所有可以這樣產生的字串，比如ba, abab, aababb, aaababbb等等。

形式語言

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

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