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

形式定義

上下文無關(guān)文法 G 是 4-元組：

G = ( V , Σ Σ --> , R , S ) {\displaystyle G=(V\,,\Sigma \,,R\,,S\,)} 這里的

1. V {\displaystyle V\,} 是“非終結(jié)”符號(hào)或變量的有限集合。它們表示在句子中不同類型的短語或子句。

2. Σ Σ --> {\displaystyle \Sigma \,} 是“終結(jié)符”的有限集合，無交集于 V {\displaystyle V\,} ，它們構(gòu)成了句子的實(shí)際內(nèi)容。

3. S {\displaystyle S\,} 是開始變量，用來表示整個(gè)句子（或程序）。它必須是 V {\displaystyle V\,} 的元素。

4. R {\displaystyle R\,} 是從 V {\displaystyle V\,} 到 ( V ∪ ∪ --> Σ Σ --> ) ? ? --> {\displaystyle (V\cup \Sigma )^{*}} 的關(guān)系，使得 ? ? --> w ∈ ∈ --> ( V ∪ ∪ --> Σ Σ --> ) ? ? --> : ( S , w ) ∈ ∈ --> R {\displaystyle \exists \,w\in (V\cup \Sigma )^{*}:(S,w)\in R} 。

此外， R {\displaystyle R\,} 是有限集合。 R {\displaystyle R\,} 的成員叫做文法的“規(guī)則”或“產(chǎn)生式”。星號(hào)表示Kleene星號(hào)運(yùn)算。

補(bǔ)充定義 1

對(duì)于任何字符串 u , v ∈ ∈ --> ( V ∪ ∪ --> Σ Σ --> ) ? ? --> {\displaystyle u,v\in (V\cup \Sigma )^{*}} ，我們稱 u {\displaystyle u\,} 生成 v {\displaystyle v\,} ，寫為 u ? ? --> v {\displaystyle u\Rightarrow v\,} ，如果 ? ? --> ( α α --> , β β --> ) ∈ ∈ --> R , u 1 , u 2 ∈ ∈ --> ( V ∪ ∪ --> Σ Σ --> ) ? ? --> {\displaystyle \exists (\alpha ,\beta )\in R,u_{1},u_{2}\in (V\cup \Sigma )^{*}} 使得 u = u 1 α α --> u 2 {\displaystyle u\,=u_{1}\alpha u_{2}} 且 v = u 1 β β --> u 2 {\displaystyle v\,=u_{1}\beta u_{2}} 。因此 v {\displaystyle v} 是應(yīng)用規(guī)則 ( α α --> , β β --> ) {\displaystyle (\alpha ,\beta )} 于 u {\displaystyle u} 的結(jié)果。

補(bǔ)充定義 2

對(duì)于任何 u , v ∈ ∈ --> ( V ∪ ∪ --> Σ Σ --> ) ? ? --> , u ? ? --> ? ? --> v {\displaystyle u,v\in (V\cup \Sigma )^{*},u{\stackrel {*}{\Rightarrow }}v} （或 u ? ? -->? ? --> v {\displaystyle u\Rightarrow \Rightarrow v\,} 在某些教科書中），如果 ? ? --> u 1 , u 2 , ? ? --> u k ∈ ∈ --> ( V ∪ ∪ --> Σ Σ --> ) ? ? --> , k ≥ ≥ --> 0 {\displaystyle \exists u_{1},u_{2},\cdots u_{k}\in (V\cup \Sigma )^{*},k\geq 0} 使得 u ? ? --> u 1 ? ? --> u 2 ? ? --> ? ? --> u k ? ? --> v {\displaystyle u\Rightarrow u_{1}\Rightarrow u_{2}\cdots \Rightarrow u_{k}\Rightarrow v} 。

補(bǔ)充定義 3

文法 G = ( V , Σ Σ --> , R , S ) {\displaystyle G=(V\,,\Sigma \,,R\,,S\,)} 的語言是集合

補(bǔ)充定義 4

語言 L {\displaystyle L\,} 被稱為是上下文無關(guān)語言（CFL），如果存在一個(gè) CFG G {\displaystyle G\,} 使得 L = L ( G ) {\displaystyle L\,=\,L(G)} 。

例子

例子 1

一個(gè)簡(jiǎn)單的上下文無關(guān)文法的例子是：S -> aSb | ab 。這個(gè)文法產(chǎn)生了語言 {a b : n ≥ 1} 。不難證明這個(gè)語言不是正則的。

例子 2

這個(gè)例子可以產(chǎn)生變量 x,y,z 的算術(shù)表達(dá)式：

例如字串 "( x + y ) * x - z * y / ( x + x )" 就可以用這個(gè)文法來產(chǎn)生。

例子 3

字母表 {a,b} 上 a 和 b 數(shù)目不相等的所有字串可以由下述文法產(chǎn)生：

這里 T 可以產(chǎn)生 a 和 b 數(shù)目相等的所有字串，U 可以產(chǎn)生 a 的數(shù)目多于 b 的數(shù)目的所有字串， V 可以產(chǎn)生 a 的數(shù)目少于 b 的數(shù)目的所有字串。

推導(dǎo)與語法樹

范式

每一個(gè)不生成空串的上下文無關(guān)文法都可以轉(zhuǎn)化為等價(jià)的 Chomsky 范式或 Greibach 范式。這里兩個(gè)文法等價(jià)的含義指它們生成相同的語言。

由于 Chomsky 范式在形式上非常簡(jiǎn)單，所以它在理論和實(shí)踐上都有應(yīng)用。比如，對(duì)每一個(gè)上下文無關(guān)語言，我們可以利用 Chomsky 范式構(gòu)造一個(gè)多項(xiàng)式算法，用它來判斷一個(gè)給定字串是否屬于這個(gè)語言（CYK算法）。

參見

上下文有關(guān)文法

形式文法

分析

分析表達(dá)式文法

隨機(jī)上下文無關(guān)文法

引用

Chomsky, Noam (Sept. 1956). "Three models for the description of language". Information Theory, IEEE Transactions 2 (3).

進(jìn)一步閱讀

Michael Sipser. Introduction to the Theory of Computation. PWS Publishing. 1997. ISBN 978-0-534-94728-6. Section 2.1: Context-Free Grammars, pp.91–101. Section 4.1.2: Decidable problems concerning context-free languages, pp.156–159. Section 5.1.1: Reductions via computation histories: pp.176–183.

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