問題タブ [language-theory]

Javaでは、コンストラクターを再帰的にすることはできません。コンパイル時エラー：「再帰的なコンストラクターの呼び出し」。この制限がなかったとしましょう。

覚えておくべきこと：

• コンストラクターの戻り型はvoidです。これは無効な方法であるため、再帰の完全な力を利用することはできません。
• コンストラクターは、this（）を使用して自分自身（または他のコンストラクター）を呼び出すことができます。しかし、「これへの呼び出しはコンストラクターの最初のステートメントでなければなりません」
• 連続する呼び出しの間に非ローカルデータを使用して、再帰的なコンストラクターから利益を得ることができます。

再帰的なコンストラクターを許可することで何かメリットはありますか？

これがプログラミングに直接関係していないことは知っていますが、次の証明に正規言語の反復補題を適用する方法を誰かが知っているかどうか疑問に思いました。

L = {（a ^ n）（b ^ n）（c ^ m）：n！=m}が文脈自由言語ではないことを示す

私はポンピング補題を適用することにかなり自信がありますが、これは本当に私を苛立たせています。どう思いますか？

ある言語を与えられた場合、それが規則的であるか、CF であるが規則的ではないか、句構造であるが CF ではないかをどのように判断しますか? この問題に対処する良い方法はありますか? ランダムに FA や PDA を作成することもできますが、もっと良い方法があると思います。

古典的な例:

L = { a^nb^nc^n | n >= 0}

どこから始めますか？ありがとう。

形式言語について疑問に思っています。私は一種のパーサーを持っています：それは、xmlのようなシリアル化されたツリー構造を読み取り、それを多次元配列に変換します。

私のポイントは、使用されているアルゴリズムとさまざまな種類のオートマトン（ステートマシンチューリングマシンスタック...）の類似点です。

したがって、問題は次のとおりです。ここで暗黙的に使用するオートマトンはどれですか。また、どの形式言語ファミリに適合しますか？そして、再帰についてはどうですか？

「暗黙的に使用するオートマトン」とは、「同じ仕事をするための最小限のオートマトン」という意味です。

完全なソースは次のとおりです。

ここでは回答せず、この質問を にコピーした cstheory.stackexchange で回答してください。

JSON と XML はどちらも文脈自由言語と呼ばれることが多く、主に EBNF の正式な文法によって指定されています。ただし、これはオブジェクト キーの一意性を必要としないRFC 4329 のセクション 2.2で定義されている JSON にのみ当てはまります (多くの人は知らないかもしれませんが、{"a":1,"a":2} は有効な JSON です!)。しかし、JSON で一意のキーが必要な場合や、XML で一意の属性名が必要な場合、これは文脈自由文法では表現できません。しかし、一意のキーを持つ JSON の言語クラスと整形式の XML (一意の属性名を意味する) はどれですか?

このテーマに関して私が見つけた最良の論文の 1 つ (Murato et al, 2001: Taxonomy of XML Schema Languages using Formal Language Theory ) では、キー/キー参照や一意性などの整合性制約が追加レイヤーでチェックされることを明示的に除外しています。これに加えて、XML スキーマまたは DTD によって定義された XML のサブセットはコンテキストフリーです。しかし、すべての整形式 XML 文書の完全なセットではありません。

ネストされたスタック オートマトン (= インデックス付き言語) は、一意のキー制約を使用して JSON を解析できるはずです。XML では、一意の整数のすべてのコンマ区切りリストの言語 S への質問を単純化できます。できれば引用して、もっと知っている人はいますか？

PS:言語を決定する単純なアルゴリズム (文脈自由部分以外) は、優れた並べ替えアルゴリズムに基づいています。したがって、最悪の場合は O(n log n) の「線形時間」で決定できるはずです。複雑さのクラスがたとえば「軽度の文脈依存」なのか「インデックス付き」なのか、まだわかりませんが、おそらく文脈自由と文脈依存の間の何か(?)です。

約束を下回り、成果を上げようとする私の絶え間ない努力の中で、プログラマーではない上司が使用できる単純な .Net アプリケーションを作成するための .Net ツールを作成しようとしています。コードを作成してコンパイルするにはどうすればよいですか?

意図の説明:バーコード ラベル アプリを作成し、いくつかのオプションを選択し、いくつかのテスト印刷を行ってから、アプリケーションを作成して再利用できるようにするように依頼するのではなく、上司に依頼してほしい。しかし、他のマシンで再利用する出力アプリケーションを作成するにはどうすればよいでしょうか?

また、これはひどい考えですか、それともメリットがありますか?

編集:私の元の質問よりも構成可能性を提案するすべての人へ: 内部使用のためにリリースするすべてのアプリは、基本的に日雇い労働者によって使用されており、上司はアプリケーションが静的で構成不可能であることを好みます。そうは言っても、私たちのアプリの中には、必要な仕様に合わせて作成されているため、5、6 年変更されていないものもあります。ここ数週間で、彼らは 2 つの新しいバーコード アプリをリクエストし、3 つ目のアプリをリクエストしました。

正規表現が文字列に対して機能するように、行列のパターンを検索できるライブラリ（任意の言語）はありますか？行列の通常の表現、または任意の行列パターン検索方法のようなものですか？

私の理解では、静的に型付けされた言語で書かれたプログラムに特定の（小さな）欠陥のサブセットがないことを正式に証明するプログラムを書くことができる可能性があるということです。

これに関する私の問題は次のとおりです。

AとBの2つのチューリング完全言語があると仮定します。Aは「タイプセーフ」であると推定され、「B」はそうではないと推定されます。Aで書かれたプログラムの正しさをチェックするためにプログラムLが与えられたとしましょう。Lを適用してBで書かれたプログラムをAに翻訳するのを防ぐにはどうすればよいですか。PがAからBに翻訳される場合、なぜPLaではないのですか。 Bで書かれたプログラムの有効な型チェッカー？

私は代数の訓練を受けており、CSの勉強を始めたばかりなので、これが機能しない明らかな理由があるかもしれませんが、私は非常に知りたいです。この「型安全性」全体は、しばらくの間私にとって魚臭いものでした。

私はプログラミング理論について読むのが好きなので、変数がいくつかの型を持つことを可能にするオブジェクト指向の静的型付き言語があれば教えていただけますか? 疑似コードの例:

このオブジェクトのメソッドを呼び出す方法を考えます。オブジェクト値の型がBigInteger |の場合 二重言語を使用すると、ユーザーは共有メソッド (レイク プラス、マイナス) のみを呼び出すことができますが、型がBigInteger | ダブル | Nilの場合、Nil のオブジェクトにはプラスとマイナスのメソッドがないため、共有メソッド (toString など) がほとんどないため、このオブジェクトでは何も役に立ちません。

では、静的型付きオブジェクト指向言語で型の少ない変数に対してメソッドを呼び出す方法はありますか?

私は問題を解決するのに問題があります:- それは課題です, 私はそれを解決しました, しかし、それは長すぎて漠然としているようです. 誰か助けてください.

a が偶数個、b が奇数個で、文字セットが {a,b} の文字列の正規表現。