問題タブ [non-deterministic]

非決定性チューリングマシンを使用して、言語が状況依存であることをどのように示すことができますか？

線形拘束オートマトン（LBA）で受け入れられる言語は、状況依存言語であることを私は知っています。また、LBAは非決定性チューリングマシンです。

これらすべてをどのように関連付けて、言語が状況依存であることを示すことができますか？

非決定論的FSMを実装する必要があるため、状態と遷移（他のFSMの状態に依存する場合と依存しない場合がありますが、イベント/入力に依存する必要があります）を保持するFSMクラスを定義するというアイデアを思いつきました。各オブジェクトと静的std::mapを、すべてのFSMが構築時に登録するクラスに追加します。このように、イベント/入力時に、各FSMは必要に応じて他のFSMの状態を検索し、すべてのFSMを1つの巨大な決定論的FSMに結合することなくそれに応じて動作できます。

これは1つのNFSMで機能します。これは私が今必要としているすべてですが、さらに必要な場合は拡張できますか？このデザインに根本的な問題はありますか？

Haskell の並行処理と並列処理のコンテキストにおける決定論をよく理解していません。いくつかの例が役に立ちます。ありがとう

ANTLR を使用しようとしています (3.3 と 3.4 を試しました)。テスト コードを実行しようとすると、奇妙なことが起こります。最初に私の非常に単純なコードを見てください。後で問題を説明します。

テスト文法:

テストコード:

コンパイル:

最初の問題は、何も印刷されないことです:)。私は Intellij IDEA (10) で作業しており、ここからコードを実行しようとしましたが成功しませんでした (CLASSPATH に ANTLR を使用)。ただし、ブレークポイントをオンint i = 1にしてデバッグし、続行する前に1〜3秒待つと、機能します! ブレークポイントなしでデバッグ モードで実行すると、実行されません。誰かが私に何が問題なのか説明してもらえますか? ありがとうございました。

編集：

だから私はあなたを入れてみました：

直後の

そしてそれはうまくいきました。しかし、その後、CommonTokenStreamコンストラクターのデバッグを開始し (数分)、乗ったときにtokens.fill()IndexOutOfBoundException が発生しました。どういうわけか、バックグラウンドで何かが何かをしましたが、IDEA に他のスレッドが表示されません。

EDIT2：

問題が解決しました。fill()最初に呼び出す必要があるようですが、BufferedTokenStreamおそらくこのように使用することを意図していませんでした。私はこのチュートリアルhttp://bkiers.blogspot.com/2011/03/2-introduction-to-antlr.htmlに従いましたが、おそらく著者にとっては何らかの形で機能していました（なぜだろうか）。IntelliJ IDEA デバッガーtoString()がローカル オブジェクトを呼び出し、それが順番に呼び出されfill()たため、ブレークポイントを設定したときに機能しました。toString()改造状態は悪です！

ListT私は現在、モナド変換子を多用するプロジェクトを書いています。プレーンリストを使用する場合、非決定性の実装は非常に簡単です。ただし、コードをに変換する必要ListTがあると、はるかに複雑になります¹。

[a]簡単な例として、からへの変換には、ListT a実際には2つの関数を作成する必要があります。

シンプルですが、まだそこにないのには驚きました。

質問：

• モナド変換子が必要な非決定性を処理するためのより良い方法はありますか？
• リスト間をきれいに行き来するためのテクニック/ライブラリはありListTますか？

¹正確な理由は非常に複雑なので、あまり詳しく説明したくありません。

XML スキーマに問題があります。

最初に、xml の可能なケースを示したいと思います。

1.

2.

3.

4.

5.

6.

ケース 5 と 6 は、presentee が設定されている場合にのみ可能です。

これを処理するためのスキーマを作成しました。

問題を処理するために、構造にいくつかの変更を試みましたが、「良い」解決策が得られません。

ウィキペディアは、決定論的ステート オートメーションは「入力文字列ごとにオートマトンの一意の計算 (または実行) を生成する」と述べています。

一意の文字列を計算するための可能なパスは1つしかないため、これを常に理解していました。その場合、以下は DSM です。

しかし今、私はこれを考え直し、説明を各入力文字列が単一の可能なパスを持ち、そのパスは他のすべての入力文字列から一意であると解釈しています。この場合、'11' と '12' は同じパスをたどるので、以下は DSM ではありません。

私の質問は、次は DSM または NDSM ですか?

アーキテクチャやブラウザが異なると、同じ数学演算でも異なる結果が返されることがありますか?

私はここでロープの終わりにいます。私はシングルスレッドの C++ プログラムを持っています。ここにいくつかの経験的データと背景情報があります。私は最も重要なキーワードを強調しようとしました。

• 私が話しているセクション全体には、標準 C++ ライブラリが実行する可能性のあるメモリ (割り当て解除) 呼び出し ( が含まれる) を除いて、syscalls はありません。これは純粋に論理的なアルゴリズムです。std::set
• これの動作は、入力に応じて決定論的である必要がありますが、私は変化しません。
• バグが明らかになった場合、プログラムは無限ループのように見えるものに陥り、境界を超えてメモリの割り当てを開始するように見えます。
• バグは予想どおりには現れません。コマンド ラインからプログラムを実行できますが、バグが現れることもあります (おそらく 30% ～ 50%)。
• プロンプトから直接プログラムを実行するのではなく、gdb または valgrind でプログラムを実行すると、バグがなくなり、プログラムが停止することはありません。
• 最良の部分は次のとおりです。問題を（テンプレート化された）非仮想メンバー関数呼び出しまで追跡しました。電話をかける直前に、ターミナルに表示されるメッセージをstd::coutに出力します。関数内の最初の行にもデバッグ メッセージがありますが、これは表示されません。

もう合理的な説明は見当たりません。進め方のヒントが得られるかもしれません。

編集:コードの重要な行。参照できるように行番号を変更し、無関係な部分を省略したため、すべてが最良の意味を持っているわけではありません。

a.cpp

b.cpp

出力の最後の行は次のとおりです。

その後、無限ループに陥ります。

mallocが 0 のメモリを返すことは保証されていません。従来の知恵は、それだけでなく、メモリmallocの戻り値の内容は実際には非決定論的であるということです。たとえば、openssl は追加のランダム性のためにそれらを使用していました。

ただし、私の知る限り、mallocはbrk/sbrkの上に構築されており、これは 0 のメモリを「返す」ものです。mallocが返す内容が、たとえば以前に解放されたメモリから0 以外である理由はわかりますが、「通常の」シングルスレッドソフトウェアではなぜそれらが非決定論的でしょうか?

1. 従来の知恵は本当に真実ですか (同じバイナリとライブラリを想定)
2. もしそうなら、なぜですか？

編集上記の質問ですでに説明したように、メモリが0以外になる理由を説明する人が何人かいます。私が求めているのは、malloc が返す内容を使用するプログラムが非決定論的である可能性がある理由、つまり、実行するたびに異なる動作をする可能性がある理由です (同じバイナリとライブラリを想定して)。非決定的な動作は、非 0 によって暗示されません。別の言い方をすれば、バイナリが実行されるたびに異なる内容になる理由です。