上下文無關文法

我需要幫助理解這個概念。上下文無關文法

書中指出

G1: 
    A→0A1 
    A→B 
    B→#

它指出G1生成字符串000#111

，並顯示一個過程

A → 0A1 → 00A11 → 000A111 → 000B111 → 000#111

我知道這裏發生了什麼英寸我不確定的是它是否可以無限循環。

例如：

可以G1也使用這種方法

A → 0A1 → 0B1 → 0#1

書中並沒有解釋這一部分作爲顯然產生0#1。謝謝

2013-03-08 juice

是的，任何生產都可以應用無數次，從而生成（在這個和大多數情況下）無限數量的字符串。此語法生成所有格式的字符串0 ⁿ＃1 ⁿ

2013-03-08 05:12:04 uba

我很感激。它實際上最終在書中說過，但是在他們給出的幾個例子後幾頁。他們正式定義了這個定義。非常感謝。 – juice 2013-03-08 05:36:30

@juice yes你注意到'A→0A1'這裏'A'可以用RHS自己生產替換這個規則使它產生無限大的0^n_1^n，'A - > B'被包括來轉換感傷形式納入句子。你可以重寫相同的語法，比如'A - > 0A1 | ＃' – 2013-03-08 19:52:17

是的。給定的語法也會生成0#1語言。事情很清楚。如您所見，生成的語言0＃1是由同一語法生成的前一種語言的子集。

2013-03-08 05:11:32

回答