CFG語法定義

Question

定義生成該語言的CFG（上下文無關語言）：

L = {a^n b^m c^n | n，m> = 0}

誰能告訴我如何解決這個問題？

我理解的是L被等製成的元件的：{aabbbcc}（I假設n = 2且m = 3）

由於事先 勒夫

Answer 1

這聽起來像家庭作業，所以我我會提供一些提示。

如何在上下文無關的語法生成中使a和c的匹配數量如何？

你可以用什麼樣的生產來生成一系列b的？

這兩個子問題怎麼可以組合成一個上下文無關文法？

Answer 2

考慮一個上下文無關文法生成該語言在G1

L1 = {a^nc^n : n >= 0} 

如

G1 = <{S},{a,c},S,{S -> aSc,S-> λ}> 

導子可如下表徵：

G1 =>1 S  (via S) 
    =>* a^nSc^n (via n >= 0 applications of S -> aSc) 
    =>1 a^nc^n (via S -> λ) 

語法G1建立之間所需的關係a's和c的語言L1的號碼和位置，然後終止於規則S -> λ的應用程序。

考慮如何在G1推導通過應用規則S -> λ終止，你怎麼可能產生的m >= 0b的，而不是空字符串的序列。這是一個稍微更一般的問題的解決方案。假設我們有文法

G2 = <V,N,S2,P> 

爲了產生L2由同等數量的a的和c的包圍串產生的語言L2的G1規則可能如下獲得來增強語法G1'：

G1' = <{S} ∪ V,{a,c} ∪ N,S,{S -> aSc,S -> S2} ∪ {P}> 

解決您的問題，讓L2是語言{b}*和G2常規語法生成它。