問題タブ [context-free-grammar]

文脈自由文法から生じる解析ツリーを描画するための優れたツールを持っている人はいますか? この質問がありますが、解析ツリーではなく有限オートマトンを具体的に扱っています。これまでgraphvizを使ってきたのですが、ノードごとに個別にラベルを付けないといけないなどちょっと面倒です。

Packrat パーサーで文字列abcを解析しようとするとします。

ここでは、Packrat パーサーでサポートされている左再帰を使用していますが、なぜ失敗するのかわかりません。パーサーのドキュメントによると P | P が成功した場合、Q は P に等しいため、この場合、次のようにab置き換えた場合と同様に、「a」ではなく「ab」に置き換える必要がありabます。

私はオランダ語のコーパスに取り組んでいますが、NLTK にオランダ語の文法が埋め込まれているかどうかを知りたいので、文章を解析できますか? 一般に、NLTK は英語でのみ機能しますか? Alpino オランダ語のコポラがあることは知っていますが、関数 (CFG を使用した解析など) がオランダ語用にも作成されていることを示すものはありません。ありがとう

このアルゴリズムが示すように、間接再帰を削除してから直接再帰を削除することにより、CFG から左再帰を削除しようとしています。

私はこの文法を使用します：

i = 1でj = 1の場合、 A -> A rの形式のすべてのプロダクションを次のように置き換えます。

A -> δ ₁ γ | δ ₂ γ | .. | δ _k γ

したがって、一致する A -> A aを見ると、次のように置き換える必要があります

どちらが間違っていると確信していますか

プロダクション自体に置き換えるときに、プロダクションを置き換える方法について誰かが正しい方向に向けることができますか?

注：また、私は最初のルールだけに固執しているので、簡単にするために他のルールを省略しました

どんな助けでも大歓迎です

[更新]元のギリシャ記号にできるだけ近いものを見つけました。また、おそらくこれに間違った方向でアプローチしていますか。i=1かつj=1の場合、A _j -> A a | ABC | 紀元前 | 紀元前 DD、しかし、A _j -> BC |を使用する必要があります。DD もしそうなら、私は得るでしょう：

これにより、そのプロダクションでの再帰が排除されます。これはより良い方向ですか？

まず第一に、これが私が求めているものの正しい翻訳であるかどうかはわかりません。

私のコースの1つでは、正規表現や形式言語などについて学び始めました。

この場合、私が1Rから始めたとしましょう。そうすれば、1Rまたは0Rのどちらかを続けていくことができます。

1Rから始めると、1 ....すると、文（この場合は2進数）は完全になりますか？後で何かを「追加」できないので、1Rと言ってから、1を選択してから、もう一度1Rを選択しますか？

よろしくお願いします。正しくない場合は、投稿にタグを付け直してください。

追加した：

1100110を生成する方法は？

これは宿題ではなく、パワーポイントからの例/質問です。それがどのように行われるのかわかりません。

私の経験に基づくと、形式文法は通常、次のような形式でコンマ区切りのリストを表します。

二度言及することを避けるためにどのような選択肢がありfooますか？この不自然な例は十分に無実に見えるかもしれませんが、私はの代わりに自明でない表現に遭遇していfooます。例えば：

言語 (たとえば、L={a^nb^mc^s | 0<=n<=m<=s}) が、通常、コンテキストフリー、再帰的、再帰的に列挙可能か、またはそれらのどれでもないかどうかを判断する必要があります。

言語が正則 (機能する DFA または正規表現を見つける) か、文脈自由 (機能する PDA または文脈自由文法を見つける) かを判断する方法を知っています。再帰言語には常に停止するチューリング マシンがあり、再帰的に列挙可能な言語には停止しないチューリング マシンがあることを知っています。

問題は、言語が再帰的か、再帰的に列挙可能か、またはどちらでもないかを判断するための迅速な基準があるかということです。たとえば、言語が文脈自由であることを理解するために PDA を構築する必要はありません。1 つのスタックが必要であるという事実からはわかりません。問題に対する同様の迅速なアプローチはありますか (チューリング マシンを構築する手間が省けることを願っています)。

私はいくつかのテスト準備資料に取り組んでいて、この問題に固執しています。

L = {we {a、b} *：w = wRであり、すべてのaの直後にab}がある場合の文脈自由文法を表示します。

wRは逆にwです。したがって、英語では、すべての「a」の後に「b」が続く回文で、任意の数のaとbを使用します。

これまでのところ、逆の部分でこれを取得しましたが、回文のプロパティが保持されていることを確認しながら、すべてのaの後にabの部分を組み込む方法がわかりません。

どんな助けでも大歓迎です！

同じ言語を受け入れることができる正規表現を与えることが不可能な CFG の例があるかどうかを調べようとしています。

紛争がどこにあるか知っている人はいますか？

アップデート

削除するexp(res) ::= exp(e1) OP(o) exp(e2).と、競合は2つだけになりますが、なぜこれが競合を引き起こしているのかわかりません...

UPDATE2

ここで大丈夫な理由：