三、請用上下文無關文法（context-free grammar）寫出一套文法規則，以產生與正規表 示式（regular expression），a*(ba*ba*)*，完全相同的語言（*符號代表可重複零到 無數次）。再用你所寫的文法規則，用最右推導（rightmost derivation），推導出 babaaabb 一句。（20 分）

詳解 (共 1 筆)

詳解 提供者：hchungw

上下文無關文法規則

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

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

css
複製程式碼
S → A A → aA | B B → bCB | ε C → aC | 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。