任何人都可以向我解釋這個上下文無關的語法嗎？

Question

我需要了解這個作業。你不會告訴我這個答案，你只是幫助我理解被問到的問題。

我讀過我的課堂筆記，這些筆記沒有很好的幫助，還有在互聯網上搜索上下文無關的語法信息。我找不到任何看起來像我所得到的東西，而且我很困惑。

如果有人能告訴我這個CFG描述了什麼，或者給我一個很好的資源來解釋這個問題，我會非常感激。

的CFG是這樣的：

S是開始符號

<S> → <A> | ε 
<A> → 0<B> | 1<A> 
<B> → 0<C> | 1<B> 
<C> → 0<D> | 1<C> 
<D> → 1<D> | 0<B> | ε 

Answer 1

CFG定義串的圖案。

這裏的字符串可以是1,0的模式（字母） CFG的規則說明如何將表達式擴展爲字母串。

<S> → <A> | ε 
<A> → 0<B> | 1<A> 
<B> → 0<C> | 1<B> 
<C> → 0<D> | 1<C> 
<D> → 1<D> | 0<B> | ε 

這裏A可擴展到0B或1A。 LHS只能擴展。

給定一個字符串，你可以驗證它是否由CFG描述。

讓我們拿1000，看看這個CFG是否描述它。

我們將從S開始，它可以擴展到A或e。

expr = S 

e是一個特殊符號，表示它的字符串終止。 我們將使用A，因爲它給了我們希望，而不是終止於e。

expr = A  (S ->A) 

A可以擴大到0B或1A。對於我們的字符串，我們將使用1A。

expr = 1A  (A ->1A) 

現在1A有A.在規則表A中查找可以擴展到0B或1A。我們將採取0B，因爲它遵循給定的字符串。所以現在我們的結果是10B。

expr = 10B (A -> 0B) 

查找B擴展到0C或1B。我們將採用0C，因爲它符合我們的給定模式。因此我們的弦變成100C。

expr = 100C (B -> 0C) 

同樣，您可以繼續擴展表達式並以e結束。

expr = 1000D (C -> 0D) 
expr = 1000e (D -> e) 

Answer 2

CFG：上下文無關文法（CFG）在形式語言理論用於描述某一類正式grammar.In上下文無關文法的一個術語，所有的規則都是一對一的，一個到很多或者一對一。由上下文無關語法生成的語言稱爲上下文無關語言（CFL）。不同的上下文無關語法可以生成相同的上下文無關語言。區分語言的屬性和特定語法的屬性很重要。語言平等問題（做兩個給定的上下文無關語法生成相同的語言？）是不可判定的。

以上線路被選擇部分從CFG

因此，在短期，在任何給定的CFG我們試圖找出一套可以在CFG描述字符串。這些字符串組成了特定CFG的語言。

下面是您的問題的圖形形式的溶液：

在溶液中，在矩形框的字符串是端接步驟。

所以給定的CFG可以具有像字符串：

{100，0100，1001，1010，01001，10011，10101，010011，0100111，......}

所以這CFG可以具有任何類型的字符串，其具有：

1. 至少一種1，
2. 至少兩個0，

3. 長度> = 3，如通過觀察，我們得到的最小長度ST環能是100：

   S --> A --> 1B --> 10C --> 100D --> 100e --> 100 
   

而且通過觀察每一個步驟就可以輕鬆搞定，這CFG可以是任何類型的字符串，具有上述三種特性的字符串。

所以這個CFG描述了一個上下文無關語言，它有3個以上的屬性。