資料結構
網路
關係資料庫管理系統(RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學在TOC中解釋語言的正式定義並舉例說明。
由文法G生成的語言是由起始符號可以匯出的所有字串（在終結符上）的集合。
示例1
設文法G由終結符集T = {a, b}、唯一的非終結符起始符號S和產生式規則集定義。因此，文法G如下所示：
S → ∧, S → aSb
或者簡寫為：
S → ∧ | aSb
L(G) = {∧, ab, aabb, aaabbb, . . . }
定義
如果G被稱為具有起始符號S和終結符集T的文法，則G生成的語言是以下集合：
S → ∧ | aSb
L(G) = {s | s ∈ T* and S ⇒+ s}.
也就是說，它是所有僅包含終結符的字串的集合，這些字串可以使用一個或多個步驟從起始符號匯出。
示例2
設∑ = {a, b, c}為終結符集，{A, S}為非終結符集，起始符號為S。∑上的語言L由以下產生式定義：
S → b | aA, A → c | bS
屬於語言L的字串示例如下：
顯然，我們可以生成b。所有較長的字串都以a開頭。所有字串都以b或ac結尾。
我們可以生成字串：b, ac, abb, abac, ababb, ababac, abababb, . . .
以下特徵描述是否正確？
“L中的任何字串都包含a、b（任意順序），並以b或ac結尾”
… 不！
例如，ba, abaabac ∉ L
示例3
設∑ = {a, b, c}為終結符集，S是唯一的非終結符。以下四個產生式描述的是什麼語言？
S → ∧
S → aS
S → bS
S → cS
或者簡寫為：S → ∧ | aS | bS | cS。
嘗試理解這些規則可以生成∑*中的所有字串，並驗證字串aacb。
S ⇒ aS ⇒ aaS ⇒ aacS ⇒ aacbS ⇒ aacb∧ = aacb
因此，S ⇒*aacb。
更新於：2021年6月15日
3K+ 次瀏覽
廣告