申論題

上下文無關文法規則

我們要用上下文無關文法（Context-Free Grammar，CFG）來產生與正規表示式 a∗(ba∗ba∗)∗a^*(ba^*ba^*)^*a∗(ba∗ba∗)∗ 相同的語言。這個正規表示式可以解讀為任意數量的 a，後跟任意數量的 ba∗bba^*bba∗b 模式，後者也可以重複任意次。

以下是與該正規表示式對應的文法規則：

規則說明

• S → A：開始規則，產生符號 A。
• A → aA | B：A 可以產生任意數量的 a，後接 B。
• B → bCB | ε：B 可以產生模式 ba∗bb a^* bba∗b 並重複任意次，也可以結束（空串 ε）。
• C → aC | b：C 產生任意數量的 a，最後接一個 b。

推導過程

我們將用最右推導（rightmost derivation）推導出字串 babaaabb。

1. 開始符號：

SSS

1. 根據規則 S → A：

S→AS \rightarrow AS→A

1. 根據規則 A → B：

A→BA \rightarrow BA→B

1. 根據規則 B → bCB：

B→bCBB \rightarrow bCBB→bCB

1. 根據規則 C → b：

C→bC \rightarrow bC→b

1. 將 C 替換為 b：

B→bbBB \rightarrow b b BB→bbB

1. 根據規則 B → bCB：

B→bbbCBB \rightarrow b b bCBB→bbbCB

1. 根據規則 C → aC：

C→aCC \rightarrow aCC→aC

1. 將 C 替換為 aC：

B→bbbaCBB \rightarrow b b b aCBB→bbbaCB

1. 根據規則 C → aC：

C→aCC \rightarrow aCC→aC

1. 將 C 替換為 aC：

B→bbbaaCBB \rightarrow b b b a aCBB→bbbaaCB

1. 根據規則 C → b：

C→bC \rightarrow bC→b

1. 將 C 替換為 b：

B→bbbaabBB \rightarrow b b b a a bBB→bbbaabB

1. 根據規則 B → ε：

B→ϵB \rightarrow \epsilonB→ϵ

1. 將 B 替換為空串：

B→bbbaabϵB \rightarrow b b b a a b \epsilonB→bbbaabϵ

最終推導結果：

S→A→B→bCB→bbB→bbbCB→bbbaCB→bbbaaCB→bbbaabB→babaaabbS \rightarrow A \rightarrow B \rightarrow bCB \rightarrow bbB \rightarrow bbbCB \rightarrow bbb aCB \rightarrow bbb aaCB \rightarrow bbb aabB \rightarrow babaaabbS→A→B→bCB→bbB→bbbCB→bbbaCB→bbbaaCB→bbbaabB→babaaabb

這樣，我們使用最右推導成功推導出字串 babaaabb。