chomsky-normal-form

1熱

1答えて

1熱

1答えて

チョムスキー標準形 - 計算理論

チョムスキー標準形（CNF）に文法を変更したい。これは私が答えについてわからないこの S --> [A] [B] [A] --> [aA] [Sb] | [a] [aA] --> [a] A [Sb] --> s [b] [a] --> a [b] --> b を解決しようとする例 S--> AB | ɛ A--> aASb | a B--> bS です。それ

3熱

3答えて

チョムスキー正規形

なぜチョムスキー正規形に変換するのですか？利点はありますか？

0熱

1答えて

チョムスキー標準形の正確

私はこれらの作品があります。 S->aSb S-> eps (eps=empty string) を私は私の推論チョムスキー標準形を適用する必要があります： 1）を考えると、EPSルール排除： S->aSb S-> eps を入手方法： S->ab S->aSb 2）排除ユニットのルールなし 3）削除無用のシンボルがあります私が取得： S->ab ので、与えられた

0熱

2答えて

チョムスキー標準形変換アルゴリズム

なぜ文法をチョムスキー正規形に変換したいのですが、新しい開始状態S0 - > Sを追加するのですか？私たちがそれをしなければ何がうまくいかないのですか？最初はイプシロンのルールのためだと思っていました。しかし、変数startからイプシロン規則を削除しません。だから、S0→Sを加えることのメリットは何ですか？ありがとうございました

1熱

1答えて

Chomsky Normal Formで文脈自由文法を構築する

Chomsky Normal Formで、唯一の文字列a^21を含む言語を受け付ける可能な限り少数のプロダクションでCFGを構築しようとしています。は、私はちょうど Sを変換することができることを理解する - > AAAAAAAAAAAAAAAAAAAAA A - > が、その後、その言語を短縮チョムスキー標準形に変換する他の方法がありますか？

4熱

1答えて

CKYは実際にCNFを必要としますか？

私はCYK/CKYアルゴリズムが文法がChomsky Normal Form（CNF）であることを要求するいくつかの場所を読んだ。 CYKの標準バージョンのみチョムスキー標準形（CNF）に与えられた文脈自由文法で動作〜Wikipedia しかし、私はまた、どこCKYアルゴリズムの多くの例を見てきました文法はCNFにはありませんでした。私ものRHSに3つの非端子を使用CKYを実証する他の例を見てき

9熱

1答えて

チョムスキー正規形の導出に2n-1ステップが必要であることを証明するにはどうすればよいですか？

私は次のことを証明しようとしている： Gはチョムスキー標準形で文脈自由文法であれば、長さN ≥ 1のL（G）を所属wが、その後、任意の文字列のために、それは正確に2n個必要ですwを導出するための-1ステップ。どうすればこのことを証明できますか？ヒントとして

3熱

1答えて

通常以外の言語と通常の言語との連結は常に規則的ではありませんか？

2つの言語の間の連結（通常のものとそうでないもの）が常に規則的でないか、出力が通常の言語であるかどうかを知りたいと思います。おかげさまで

3熱

2答えて

チョムスキー普通形に変換

私はあなたの助けが必要です。 1) A--> aAb 2) A--> bAa 3) A--> ε 私はチョムスキー標準形（CNF）を適用する必要がありますは、私はこれらの作品を持っています。私がすべき上記のルール適用するためには：εproducions を排除は、単一の制作を排除すぐに私は動けなく無用のシンボルを削除します。その理由は、Aはnull可能なシンボルです（εはボディの