誰もこの文脈自由文法を私に説明できますか？

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、e（アルファベット）のパターンになります CFGの規則は、式をアルファベットの文字列に展開する方法を示します。ここでA

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

は 0Bまたは 1Aに拡張することができます。 LHSは拡大のみ可能です。

文字列を指定すると、CFGによって記述されているかどうかを確認できます。

1000をとり、このCFGで記述されているかどうかを確認してください。

まず、Aからeに展開できるSから始めます。

expr = S 

eは、文字列の終了を示す特別な記号です。 eで終了する代わりに、私たちに希望を与えるので、Aを使用します。

expr = A  (S ->A) 

Aは0Bまたは1Aに拡張できます。私たちの弦については、1Aを使用します。

expr = 1A  (A ->1A) 

ここで1AにはAがあります。ルールテーブルAを参照すると、0Bまたは1Aに展開できます。指定された文字列に続いて0Bをとります。だから私たちの結果は10Bです。

0Cまたは1Bに展開されるルックアップB。私たちは与えられたパターンと一致するので0Cを取り上げます。したがって、私たちの文字列は100Cになります。

expr = 100C (B -> 0C) 

同様に、式を展開してeで終了できます。

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

Answer 2

はCFG：文脈自由文法（CFG）は、正式なgrammar.In文脈自由文法の特定のタイプを記述するために形式言語理論で使用される用語である、すべてのルールは、一対一の一つであります文脈自由文法によって生成される言語は、文脈自由言語（CFL）として知られている。異なる文脈自由文法は、同じ文脈自由言語を生成することができる。言語の特性を特定の文法の特性と区別することが重要です。言語平等問題（2つの文脈自由文法は同じ言語を生成するか）は決めることができません。私たちはそのCFGに記述できる文字列のセットを見つけることを試みる与え

上記の行は、任意のCFGから、短期でそうCFG

から一部を選択しています。これらの文字列は、その特定のCFGの言語を作成します。溶液中では

は、長方形のボックス内の文字列は終端手順は次のとおりです。

以下はグラフ形式であなたの質問のソリューションです。

{100、0100、1001、1010、01001、10011、10101、010011、0100111、...}だから

このCFG：

したがって所与CFGのような文字列を持つことができ

1. 少なくとも一つの1を、少なくとも2 0
2. 、および

3. 長さ> = 3、観察することによって、私たちは最小の長さを得るようST：持っている文字列の任意の型を持つことができますリングは100になります

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

、各ステップでの文字列を観察することによって、あなたは簡単にこのCFGは、3つのプロパティの上に持っていた文字列のいずれかのタイプを持つことができることを得ることができます。

このCFGは、上記の3つのプロパティを持つコンテキストフリー言語を記述します。