問題タブ [chomsky-normal-form]

1. 正規言語のポンピング補題を使用して、

   言語 L = { a ⁱ , b ^j c ^k | i、j、k は非負の整数で、i=j または i=k }

規則的ではない

2. 上記の言語の CFG を設計する

これが私が思いついたものです

今、私は問題を抱えているチョムスキー正規形に上記のCFGを変換する必要があります...助けはありますか?

CNF 変換の最初のステップをいつ使用するかについて混乱しています。

最初のステップ:ensure s does not appear on rhs, add new S0 if necessary and copy all rules of S

上記のステートメントが何を意味するのか、私には明確ではありません。S0を作成するタイミングがわかりません。S0 で始まらない CFG もあれば、S0 で始まる CFG もあります。

ここで少し助けてください。

私は現在 CNF について学んでいて、少し混乱しています。

この文法を考えると：

S -> ab | aSb

CNF になります。

S -> AB | XB

X -> AY

Y -> AB | XB

A -> a

B -> b

これはどう：

S -> c | aSa | bSb

誰かがこれで私を少し後押ししてくれませんか。ありがとう。

文脈自由文法 G = ( { S, B, E }, { 0, 1, i, e, s }, R, S ) を考えてみましょう。ここで、R は次のとおりです。

わかりましたので、ラムダを削除して取得しました：

そして今、ユニット/チェーンルールと残りを削除しようとしています.これは私がこれまでに持っているものです:

しかし、私は S0 --> X と S --> BSE が無効であることを知っています。どうすればこれを修正できますか? 助けてくれてありがとう！:)

CFG を Chomsky Normal Form に変換する作業を行っていますが、問題が発生しています。

私はこのCFGを持っています

A-> BAB|B|epsilon B -> 00|epsilon

わかりました、新しい開始状態を追加します

S -> A A-> BAB|B|epsilon B -> 00|epsilon

次に、イプシロン遷移を削除する必要があるため、B から始めます

S -> A A-> BAB|B|AB|BA|A|epsilon B -> 00

次に、Aからイプシロンを削除するにはどうすればよいですか? 開始にイプシロンを含めることはできますか? そして、どうすれば A-> A に変換できますか?

次のような一連の文法生成物を nltk.cfg にフィードして、CNF 文法を使用しようとしています。

しかし、プロダクションの左側にパイプがあるプロダクションには問題があります (エラーが発生します: 矢印が必要です)。例：

nltk には、左側のパイプで問題のない文法メソッドはありますか?

そうでない場合、最初のグループのようにすべてのプロダクションを使用可能なプロダクションに変更するにはどうすればよいですか? 例：

チョムスキー標準形 (CNF) を抽出しようとしています - 構文木から文の文法生成:

ツリー全体を S という名前の文字列に入れてから、次のようにします。

出力は

しかし、一部の作品 (7 番と 8 番) は CNF ではないようです! 何が問題ですか？

この CFG を考えると

私のCNFへの変換の試み

最初に Null プロダクションを削除します。つまり、S->^ と C->^

なので取り外した後

S->B、A->C、S->A、および C->S などの単位生産を削除

これらのプロダクションを追加する

ここで、K->q、U->p

CNFに必要なCNGは

R->UC

これは正しいですか？

Y として Z のみが終端として ε が Y に移動すると考えるのは正しいでしょうか?

それから？

私は文法にこの規則を持っています:

このPCFG(Probabilistic Context Free grammar)をCNF(Chomsky Normal Form)に変換したい

そのためには、ルールを 2 つの非終端記号に分割できることを知っています。

各ルールに設定する確率は?

ありがとう