問題タブ [language-theory]

3型文法以下の実言語クラスはないとずっと思っていたのですが、正規言語ではなくパターン言語を学習できる「極限言語識別」モデルを見つけました。

パターン言語とは正確には何ですか?また、通常の言語との違いは何ですか?

私は理論の授業でこれを検討していますが、正規表現のコンパイルが実際に何であるかを知っている人がどれだけいるか興味があります。私はオンラインで調べましたが、これは私が思っていたより古風なトピックのようです。

ええ、この質問を読む前に、正規表現のコンパイルが正規表現をイプシロン非決定論的有限オートマトンに変換することによって実行されることを誰が知っていましたか? それが何なのかわからないのは誰ですか？

手始めに、これは宿題の質問です。アイデアはありますが、それでも正しい答えを得ることができません。私は答えを求めているのではなく、質問に答えるために助けを求めているだけです。

私は現在、その言語の文脈自由文法を書き込もうとしています。

したがって、基本的には、2の間にbとadの2倍のaがあります。次に例を示します。

これが私が持っているものについてです、私はあまり持っていません...私はこれらのCFGの概念を理解しています。私はこの質問の論理についてよくわかりません。私が正しい方向に進んでいるかどうかはわかりません...

ありがとう。

正規表現と文脈自由文法の共通部分が空かどうかを出力するアルゴリズムを探しています。この問題は決定可能であることはわかっていますが、実装例 (疑似コード) が見つかりません。

可能であれば.NETでそのようなアルゴリズムを誰かが提供してくれますが、これは必須ではありません。この問題は「通常の交差点」とも呼ばれます。グーグルで調べても、幾何学的アルゴリズムまたはそれに関する理論しか得られません。

編集：

誰でも。私は本当にそれに固執していて、まだ何も見つかりません。

コンテキストフリー言語をプッシュダウンオートマトンに変換するためのアプレットまたはプログラムをオンラインで見つけることができません...どんな助けでも大歓迎です。

s00、s01、s10、s11 の 4 種類のステートメントを含む言語があります。先頭の 1 は最初のキーワードを意味し、末尾の 1 は終了を意味し、区切り記号「;」があります。「;」でステートメントを終了できます。「;」の使用を最小限に抑えるステートメントのリストを許可する言語を解析したいと思います。パーサーは GLR+ である Dypgen です。

例：

これを行うことはまったく可能ですか？もしそうなら、どのように？そうでない場合、なぜですか？

主にそれを行う方法を考えられないため、それを行うことはできないと思います:)しかし、それは文脈に依存しているようです:ルールは、「;」を挿入する必要があるということです。A が終了せず、B が開始されていない場合は、A と B の間で、B と C についても同様で、B が 2 回使用されることを意味します。

ただし、パーサーは GLR+ であるため、単純に使用したくなる

ルールとして、そしてそれが誤って解析された場合は「;」をスローします (これは s11 no-op です) あいまいさを解決します。ただし、パーサーが構文エラーを報告する方がよいでしょう。おそらくこれは、代替のプロダクションをマージするときに実行できます。本当の問題は、マージではなくオーバーラップする場合です。これが発生すると、プログラムの解析が爆発する可能性があります。

私はいくつかの計算理論について（宿題ではなく）ブラッシュアップしていて、この問題に遭遇しました：

通常の言語のセットが文脈自由言語のセットの適切なサブセットであることをどのように証明できますか。

これで、言語が有限オートマトンによって受け入れられれば、その言語は規則的であることがわかりました。

また、プッシュダウン オートマトンによって受け入れられる言語は文脈自由であることも知っています。

しかし、私は解決策が何であるかわかりません。

インターフェイスの範囲について、他のプログラマーと争っています。

次のものがあるとします。

したがって、問題は次のとおりです。1.他の何かがfooInterfaceインスタンスを解放する前に、fooClassInstanceがスコープ外になる可能性はありますか？

オブジェクト（fooClassInstance）がスコープ外になる可能性があると主張する人もいます。

私はそれができないと信じています。確かに、オブジェクトがスコープ内にないとGCが判断した場合、オブジェクトはGCによって破棄される場合とされない場合があります。ただし、インターフェイスは設計上、それを使用するオブジェクトによってメンバーを実装する必要がある抽象コントラクトであるため、インターフェイスが使用されている限り、インターフェイスはその実装を失うことはありません。「interface」タイプの別のオブジェクトが作成されるわけではありません。インターフェイスは、実装者の抽象メンバーへのポインタにすぎません。

この論争を解決するのを手伝ってくれませんか。

ありがとう、

実際の現代の正規表現は実際にどのクラスの言語を認識しますか？

後方参照（例(.*)_\1）を持つ無制限の長さのキャプチャグループがある場合は常に、正規表現が非正規言語と一致するようになりました。しかし、これだけでは、次のようなものに一致させるのに十分ではありませんS ::= '(' S ')' | ε—ペアのペアを一致させる文脈自由言語。

再帰的な正規表現（これは私にとっては新しいものですが、PerlとPCREに存在すると確信しています）は、少なくともほとんどのCFLを認識しているように見えます。

誰かがこの分野で何か研究をしたか読んだことがありますか？これらの「最新の」正規表現の制限は何ですか？彼らは、LLまたはLR文法のCFGよりも厳密に多いか厳密に少ないかを認識していますか？または、正規表現では認識できるがCFGでは認識できない言語とその逆の言語の両方が存在しますか？

関連する論文へのリンクをいただければ幸いです。

数学者が私に、言語さえあればプロジェクトは可能だと言ったことがある。私たちができるときとできないときをどのように知っているかを理解するのを手伝ってもらえますか? 例のように、または自動化されたテストが「言語」とそうでないものを認識できるかどうか。ありがとう