問題タブ [computation-theory]

{0,1}両側から同じように読むことができないアルファベット上のすべての単語の言語が文脈自由言語であるかどうか（つまり、特定の文法に変換できるかどうか）を決定する際に、あなたの助けが本当に欲しいです。ルール）。{ w | w <> wR }

正規言語の反復補題によって文脈自由言語ではないことを証明しようとしましたが、矛盾につながる文字列は見つかりませんでした。

助言がありますか？

私はこれら2つの違いを理解するのに本当に苦労しています。私の教科書から、それは本質的に次のように違いを説明しています

言語がチューリング認識可能な言語の補数である場合、その言語は共チューリング認識可能です。

私が理解していないこの定義の部分は、チューリング認識可能な言語の補完である場合、それはどういう意味ですか?

それが別の言語の補数であるかどうかをどのように正確に判断しますか?

ミルナーの円周率計算では、複数のプロセスが同じチャネルから読み取るときの評価セマンティクスは何ですか?

ルールはそう言っている

!x(a). P | ?x(b) Q ~> P | Q[a/b]

しかし、次のような状況はどうですか

!x(a). P | ?x(b) Q | ?x(c) R

?

有名な紙PRIMES is in Pを勉強して混乱してください。

提案されたアルゴリズムの最初のステップは次のとおりです。アルゴリズムIf (n=a^b for nature number a and b>1), output COMPOSITE.全体が多項式時間で実行されるため、このステップもO（（log n）^ c）で完了する必要があります（入力サイズがO（log n）の場合）。ただし、理解できません。グーグルした後にターゲットをヒットするアルゴリズム。

質問：

多項式時間で他の数の指数であるかどうかをテストするために利用できるアルゴリズムはありますか？

よろしくお願いします！

文脈自由言語のコレクションの和集合は常に文脈自由ですか？あなたの答えを正当化してください.....

答えがイエスであることは知っていますが、どうすればそれを証明できますか？

次のような入力ファイルを受け取る Turing Machine Simulator を C++ で設計する必要があります。

Q:q1,q2,q3,q4
A:0,1
Z:0,1,x
T:q1,0,q2,x,R
T:q1,1,q2,x,R
T:q2,0,q2 ,0,R
...
S:q1
F:q3,q4

ここで、Q は状態、A は入力値、Z はテープのアルファベット、S は開始状態、F は受け入れ状態と拒否状態です。

入力の数、入力文字列、および受け入れまたは拒否を受け取る入力を処理する必要があります。

したがって、入力が次の場合:
3
0,#,1,1
1,1
0,1,0

出力には、ステップと、それが受け入れるか拒否するかが出力されます。

算術演算を実行する TM、文字列演算を実行する TM、および選択した別の TM を作成する必要があります。

開始方法に関するヘルプは大歓迎です。

私はアルゴリズムは得意ですが、リアルタイムの問題を変換して学習し、それをアルゴリズムとして作成することは得意ではありません。状況をわかりやすく説明し、それをアルゴリズムとして定式化することを教えたり、させたりする本/論文があるかどうかを知りたいです。（これは、状況を打破し、アルゴリズムをサクサクと思いつくための精神的能力を訓練するようなものです。）

これらの種類の問題にアプローチする方法のいくつかを示します。簡単な学習リンク/資料は、私を大いに助けてくれます。

注: SO が意見や漠然としたものを求めることを許可していないことは承知しています (Q がダウングレードされてもかまいません)。しかし、私はいくつかの具体的な問題を尋ねており、ここにいる偉大な頭脳の何人かから素晴らしい情報を得ることができることを願っています.

ほとんどが文脈自由言語でコーディングしている場合、チューリングマシン（帰納的可算言語を受け入れる）の出力をどのようにシミュレートできるかを本当に理解できません。

関連する質問:

• 数値のリストを 2 つの等しい合計リストに分割するアルゴリズム
• リストを 2 つの部分に分割し、それらの合計が互いに最も近くなるようにします

2k正確に要素を含むリストがあるとしましょう。ここで、それを 2 つの部分に分割します。各部分の長さは ですが、部分kの合計ができるだけ等しくなるようにします。

簡単な例: [3, 4, 4, 1, 2, 1]に分割される可能性が[1, 4, 3] and [1, 2, 4]あり、差額の合計は1

ここで、パーツが任意の長さを持つことができる場合、これは分割問題のバリエーションであり、弱いことがわかっています。NP-Complete.

しかし、リストを等分に分割することに関する制限(常にkとであるとしましょう2k) は、この問題を多項式時間で解決できるようにしますか? それに対する証拠はありますか（またはそれがまだであるという事実の証明スキームNP）？

テンプレートメタプログラミングでは、再帰が誤って実装され、結果として無限ループが発生した場合、言語コンパイラはそれを検出できますか？それとも、コンパイラは最終的にスタックオーバーフローに遭遇してクラッシュするのでしょうか？私の考えでは、コンパイラーはこれを検出できないでしょう。なぜなら、そうすることは停止性問題の決定不可能性に違反するからです。

私は結論で正しいですか？もちろん、これをコードで試すこともできますが、この場合は、より適切な考え方を聞きたいと思います。

編集：みんなありがとう、私はtmpの計算理論の側面に関する私の推論が間違っていなかったという一般的な考えを得る。また、コンパイラの実装には任意の再帰深度制限がある可能性があることも理解しています（もちろん、この2番目の部分をテストできたことを繰り返しますが、それは私の副次的な点にすぎません）。