什麼是上下文無關文法？舉例說明

上下文無關文法 (CFG) 是一種形式文法，用於生成給定形式語言中所有可能的字串模式。

它被定義為四個元組 -

G=(V,T,P,S)

• G 是一個文法，它包含一組產生式規則。它用於生成語言的字串。
• T 是終結符的集合。它用小寫字母表示。
• V 是非終結符的集合。它用大寫字母表示
• P 是一組產生式規則，用於將字串中的非終結符（產生式左側）替換為其他終結符（產生式右側）。
• S 是用於推匯出字串的起始符號

示例

為在集合∑={a} 上具有任意數量 a 的語言構建 CFG

解決方案

正則表示式= a*

正則表示式的產生式規則如下 -

S->aS 規則 1

S-> ε 規則 2

現在，如果我們想推匯出字串“aaaaaa”，我們可以從起始符號開始

從起始符號開始

正則表示式=a* 可以生成一組字串 { ε,a,aa,aaa,...}

我們可以有一個空字串，因為 S 是起始符號，規則 2 給出 S-> ε

Bhanu Priya

更新於: 2021年6月11日

45K+ 瀏覽量

啟動你的 職業生涯

透過完成課程獲得認證

開始學習