資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究給出一些非正則的上下文無關語言的例子。
上下文無關文法 (CFG) 由一組有限的語法規則組成，是一個四元組 **(V, T, P, S)**
其中：
V 是變數（非終結符）。
T 是一組終結符。
P 是一組規則，P: V→ (V ∪ T)*，即產生式規則的左端。P 不具有任何右上下文或左上下文。
S 是起始符號。
使用任何語言的規則，我們可以推匯出該語言中的任何字串。
對於語言 a*，CFG 如下：
S -> aS
S -> ɛ
這裡：
S 是變數。
a 和 ɛ 是終結符。
S 是起始符號。
使用這些規則，我們可以推匯出任意數量的 a。
例如，考慮字串 aaaaa 的 CFG 如下所示：
S aS rule 1 aaS rule 1 aaaS rule 1 aaaaS rule 1 aaaaaS rule 1 aaaaaɛ rule 2 aaaaa
上下文無關語言是由上下文無關文法建立的，它包含正則語言。
相同的上下文無關語言可以由多個上下文無關文法生成。
示例 1
一個非正則但屬於上下文無關語言的例子是 **{ anbn | n >= 0 }**
上述例子包含所有 a 和 b 數量相等的字串，符號 a3b3 可以擴充套件為 aaabbb，其中有三個 a 和三個 b。
抽吸引理 (Pumping Lemma) 提供了進行否定測試的能力。如果語言不滿足抽吸引理，則可以說它不是上下文無關的。抽吸引理是一個數學證明，將其應用於上下文無關語言需要時間。
示例 2
考慮另一個非正則的上下文無關語言的例子。
S -> aSb | ɛ
這個例子不是正則的，因為我們無法用有限狀態機或正則表示式來表達它。我們應該能夠計算 A 的數量並檢查 B 的數量是否匹配。此外，由於 n 可以是任何值，因此無法用有限狀態機來完成。
更新於：2021年6月16日
2K+ 次瀏覽
廣告