CFG は文脈自由文法の略です。これは、指定された形式言語で文字列の可能なすべてのパターンを生成するために使用される形式文法です。文脈自由文法 G は、次の 4 つのタプルで定義できます。
G = (V, T, P, S)
どこ、
G は文法であり、一連の生成ルールで構成されます。言語の文字列を生成するために使用されます。
T 端子記号の最終セットです。小文字で表されます。
で 非終端記号の最終セットです。大文字で表されます。
P は、文字列内の非終端記号 (プロダクションの左側) を他の終端記号または非終端記号 (プロダクションの右側) に置き換えるために使用される一連のプロダクション ルールです。
npドット
S 文字列を導出するために使用される開始記号です。すべての非終端が終端記号に置き換えられるまで、プロダクションの右側で非終端を繰り返し置換することで、文字列を導出できます。
例 1:
集合 ∑= {a} にわたって任意の数の a を持つ言語の CFG を構築します。
解決：
ご存知のとおり、上記の言語の正規表現は次のとおりです。
r.e. = a*
正規表現の作成規則は次のとおりです。
S → aS rule 1 S → ε rule 2
ここで、文字列「aaaaaa」を導出したい場合は、開始記号から始めることができます。
S aS aaS rule 1 aaaS rule 1 aaaaS rule 1 aaaaaS rule 1 aaaaaaS rule 1 aaaaaaε rule 2 aaaaaa
そこには。 = a* は文字列 {ε, a, aa, aaa,....} のセットを生成できます。 S は開始記号であり、ルール 2 は S → ε を与えるため、NULL 文字列を持つことができます。
例 2:
正規表現 (0+1)* の CFG を構築します。
解決：
マーク・ザッカーバーグの教育
CFG は次のようにして与えられます。
Production rule (P): S → 0S | 1S S → ε
ルールは、0 と 1 とスタート記号の組み合わせです。 (0+1)* は {ε, 0, 1, 01, 10, 00, 11, ....} を示しますので。このセットでは、ε は文字列であるため、ルールではルール S → ε を設定できます。
例 3:
言語 L = where w € (a, b)* の CFG を構築します。
解決：
特定の言語に対して生成できる文字列は、{aacaa、bcb、abcba、bacab、abcbba、...} です。
アルファベータ枝刈り
文法は次のようになります。
S → aSa rule 1 S → bSb rule 2 S → c rule 3
ここで、文字列「abbcbba」を導出したい場合は、開始記号から始めることができます。
S → aSa S → abSba from rule 2 S → abbSbba from rule 2 S → abbcbba from rule 3
したがって、この種の文字列はどれも、指定された生成ルールから派生できます。
例 4:
言語 L = a の CFG を構築するnb2nここで、n>=1。
解決：
特定の言語に対して生成できる文字列は、{abb, aabbbb, aaabbbbbb....} です。
文法は次のようになります。
S → aSbb | abb
ここで、文字列「aabbbb」を導出したい場合は、開始記号から始めることができます。
S → aSbb S → aabbbb