私は最終試験に向けて勉強していて、ウィキペディアの文脈自由文法の記事を読んでいて、次の例に出くわしました。
S → SS- (1st production rule)
S → (S) - (2nd production rule)
S → () - (3rd production rule)
左右の派生がよくわかります。この問題を解決しようとしたとき、開始記号から始めます
S-> SS -> (S)S-> ()S-> ()(S) -> ()()
でも答えを見たらこんな感じでした
S → SS → SSS → (S)SS → ((S))SS → ((SS))S(S)
→ ((()S))S(S) → ((()()))S(S) → ((()()))()(S)
→ ((()()))()(())
私の答えの何が問題なのかわかりませんか？最初の生産規則を 2 回使用する必要がありますか? 誰でもこれで私を助けてくれませんか。
あなたのアプローチに「問題」はありません。ウィキペディアの記事とは異なるシンボルのシーケンスを導き出しただけです。
重要な点は、文法を使用して一致するネストされた(()括弧の任意のシーケンスを導出できるが、またはのようなシーケンスを導出できないこと)()(です。
この問題を解決しようとしたとき、開始記号から始めます
何の問題？ウィキペディアの記事は問題ありません。よく一致する括弧の言語を説明する文法を示し、その言語の単語の例とその派生方法を示しているだけです。
S-> SS -> (S)S-> ()S-> ()(S) -> ()()
それは完全に有効な派生です。
でも答えを見たらこんな感じでした
それは答えではありません (質問はありませんでした)。これはほんの一例です。
私の答えの何が問題なのかわかりませんか？
あなたの派生に問題はありません。()()とは両方とも((()()))()(())、その言語で有効な単語です。
最初の生産規則を 2 回使用する必要がありますか?
プロダクション ルールは、必要に応じて何度でも適用できます (もちろん、置き換えたい非終端記号が用語に存在すると仮定します)、任意の順序で適用できます。それはすべて、派生させたい単語に依存します。
この記事は、その文法を使用して表現できる1つの可能な文字列を単に提供しています...別の可能な文字列を提供しています。派生を使用して、これらの文字列が文法に従って有効であることを証明できます (つまり、逆方向に進みます)。
編集：パンチに殴られた：P