問題タブ [context-free-language]

それは、非決定論的な文脈自由言語だけがユニオンの下で閉じられているということですか? では、ほとんどすべての教科書やサイトで、CFL は一般にユニオンの下で閉鎖されていると言及されているのはなぜですか? 直感的な説明で十分です。詳細な証明は必要ありません。

ネストと不等式を持つ文脈自由文法の例を見つけることができませんでした。

たとえば、次の CFG を作成しようとしています。

{aibjckdl : (i < l) ^ (j < k)}

したがって、 の場合、CFG は単純に次のようになります。{aidl : (i < l)}

S -> aSd | dS | d

b と c についても同様です。しかし、2 つの文法をネストする方法がわかりません。同様の例やポインタは役に立ちます。

(a,zo/azo) が q1 に移行し、(a,z0/eplison) が最終状態に移行する状態があるため、決定論的であってはなりません。これは本当ですか？

私はこの形式主義のリストを持っており、表現力に従って並べる必要があります。また、そのうちの 1 つは実際には属していません。

以下の方法で注文しました。

4のものが最も強力です。また、LR 文法を削除しました。これは、LR パーサーで解析できるように CFG を記述する方法にすぎないためです。

ただし、これが正しいかどうかはわかりません。

文法をチョムスキー標準形に変換したいときに、新しい開始状態 S0 -> S を追加するのはなぜですか? そうしないと何がうまくいかないのでしょうか？

最初はイプシロンの法則によるものだと思っていました。ただし、開始変数からイプシロン ルールを削除しません。では、S0 -> S を追加する利点は何ですか?

ありがとう

みんなさん、こんばんは！Perl の正規表現のファンとして、Google で検索しても答えられない質問を思いつきました。

それでは、私の問題の最小限の例を挙げましょう。

私は2つのテキストファイルを持っています:

ファイル A.txt:

ファイル B.txt:

特定の文脈自由言語によって生成された単語であるかどうか、各ファイルの内容を確認したいと思います。たとえば、この場合: L={a^nb^n | n > 0} .

Perl は通常の言語ではないため、Perl の正規表現が機能しないという問題があります。確かに、小さな PDA のスクリプトを作成して、終了するかどうかを確認できます。

しかし、Perl でこの問題を解決する別の方法はありますか? おそらく、文脈自由文法または sth. を渡す方法ですか?

"k" 個の 0 の後に "k+4" 個の 1 が続く文字列を照合したい (k はゼロ以上)

次の文法を試してみましたが、これは正しいですか?