問題タブ [computation-theory]

否定、補完、反転など、どのように呼ばれているのかわかりません。コンセプトはこうです。たとえば、アルファベット「ab」を持つ

この簡単な例では、次のようになります

そのような正規表現はどのように呼ばれますか? それを計算する方法があることを私の研究から覚えていますが、それは複雑で、一般的に手で作るのは難しすぎます. それを行うための優れたオンライン ツール (または通常のソフトウェア) はありますか?

私と友人は、興味深いコンピューター サイエンスの質問について熟考しています。

シンプルな2D Arrayがあります:

次に、この配列を取得して、配列内のすべての要素をシャッフルします。

最初はかなり単純な概念。しかし、もう一歩踏み出すとどうなるでしょうか。ここで、新しい配列の要素が、元の配列でカーディナル方向に隣接していた項目の隣にならないように、元の配列をシャッフルします。

1 は 2 の隣にあり、元の配列でも 2 の隣にあるため、最初のシャッフルは失敗します。

これが実際の例です：

それでも悪くない。さて、本当の質問に！

元の配列を再びシャッフルして、配列の要素が基数方向または対角線のいずれかで隣接していた要素の隣にならないようにします。

1 は斜めに 5 の隣にあり、元の配列では 5 の隣にあるため、この作業例は失敗します。

いくつかの考え:

1. 配列を決定することさえできますか?
2. 配列のサイズに依存しますか？
3. 配列は対称である必要がありますか?
4. 配列には偶数/奇数の要素が必要ですか?
5. サイズM x Nのすべての配列に解が適用されますか?
6. 解決策がある場合、新しいアレイを見つけるのにかかる時間はどれくらいですか?

どう思いますか？

編集

私の質問が「トピック外」として閉じられていることに驚いています。FAQによると、私の質問が「...一般的に特定のプログラミングの問題をカバーしている...」場合、それは尋ねられることが許可されており、「トピック外」ではありません。

私が求めていた最終的な質問は次のとおりです。

「2D配列を取り、それをシャッフルして、対角線を含め、新しい配列でメンバーが互いに隣り合わないようにすることはできますか」.

それは良いプログラミングの質問ではありませんか? 私の質問はクローズされるべきではないと強く感じています。

アルファベット{ab}上のスリーステートFAが有限の言語を持っているかどうかをテストするために、56個の文字列を記述する方法を理解しようとしています。

56という数字は、マシンにN個の状態があり、アルファベットにm個の文字がある場合、合計でm ^ N + m ^（N + 1）+ m ^（N + 2）+になるという定理に基づいています。 .. + m ^（2N-1）N<=文字列の長さ<2Nの範囲の異なる入力文字列。したがって、2 ^ 3 2 ^ 4 2 ^ 5=56文字列。

マシン上で実行することですべてをテストできることを私は知っています。受け入れられるものがあれば言語は無限であり、受け入れられない場合は言語は有限です。

文字列の説明方法がわかりません。どんな助けでも大歓迎です！

私が取り組んでいるプロジェクトでは、ランダムなアルゴリズムを生成して実行できるようにしたいと考えています (信じてください、それには十分な理由があります!)。これを理解する現代的な方法は、すべてのプログラムがバイナリで一意の大きな長い数にコンパイルされることです)。

私が非常に大きな数を持っているとしましょう。これに対応するプログラムを実行するにはどうすればよいですか?

ここでは言語はそれほど重要ではありません。これを簡単にするメカニズムが含まれている場合は、他の言語よりもいくつかの言語を選択できれば幸いです。どの言語を選んでも難しい場合は、Java が最も得意です。

ランダムなアルゴリズムを生成する別の方法を提案した場合も問題ありませんが、最終的にはロジックを変更して、純粋なランダム性ではなくヒューリスティックを使用してアルゴリズムを選択することに注意してください.

私は代入計算の理論に取り組んでいます。

質問があります p ∈ N、p > 4 とします。Q = {0, 1, . . . , k}, k ≥ p であり、すべての状態 q ∈ Q に対して、δ(q, a) = q + 1 mod p となるような a ∈ Σ が存在します。これらの条件では、(a) n に関する帰納法によって示されます。すべての n ≥ 0 および q < p に対して、δ(q, a^(n·p)) = q;

q + 1modp ....これはただの 1 ではないので、私は混乱しています。もしそうなら、これは私の質問を証明できないように思われる

任意の正規表現を同等のCFGルールのセットに変換できるアルゴリズムの概要を教えてもらえますか？

（a | b）*などの基本的なものに取り組む方法を知っています。

ただし、特に多くのネストされた操作を持つ可能性のあるより複雑な式では、適切なアルゴリズムに形式化するのに問題があります。

フォーマル言語のチョムスキー分類では、Non-Linear, Unambiguous and also Non-DeterministicContext-Free-Language(N-CFL) の例が必要ですか?

1. 線形言語:線形文法が可能なもの ( ⊆ CFG) 例:
   L ₁ = {a ⁿ b ⁿ | n ≥ 0 }

2. Deterministic Context Free Language(D-CFG) : Deterministic Push-Down-Automata(D-PDA) が可能な言語 (例:
   L ₂ = {a ⁿ b ⁿ c ^m | n ≥ 0, m ≥ 0 }
   L ₂は明確です。

線形でないCF 文法は非線形です。
L _nl = {w: n _a (w) = n _b (w)} も非線形 CFGです。

-- 3. Non-Deterministic Context Free Language(N-CFG) :only Non-Deterministic Push-Down-Automata(N-PDA)可能な例
L ₃ = {ww ^R | w ∈ {a, b} ^* }
L ₃も Linear CFG です。

--4. あいまいな CFL : only ambiguous CFG is possible
L ₄ = { a ⁿ b ^{n cm} | n ≥ 0, m ≥ 0 } U { a ⁿ b ^{m cm} | n ≥ 0, m ≥ 0 }
L ₄は非線形かつ曖昧な CFG であり、すべての曖昧な CFL \subseteq N-CFL.

私の質問は次のとおりです:
すべての非線形、非決定論的 CFL は曖昧ですか? そうでない場合は、非線形で非決定論的な CFL であり、明確な例が必要ですか?

以下にベン図を示します。

ここでも質問

CLRS の 264 ページの下部で、著者は、 を取得した後r0 = 17612864、 の最上位 14 ビットがr0ハッシュ値 を生成すると述べていますh(k) = 67。1000011バイナリの67は7ビットなので、なぜ67になるのかわかりません。

編集 教科書では: 例として、 があるとしますk = 123456, p = 14, m = 2^14 = 16384, and w = 32。Knuth の提案を適用して、A を にs/2^32最も近い形式の分数として選択(\sqrt(5) - 1) / 2しますA = 2654435769/2^32。それからk*s = 327706022297664 = (76300 * 2^32) + 17612864、などr1 = 76300 and r0 = 17612864。の最上位 14 ビットがr0値を生成しますh(k)=67。

基本的な原始再帰関数をたくさん書いている課題があります。そのうちの1つは減算です。私は前任者の定義を提供されていなかったので、それをと定義できる可能性は低いと思いますeval Pred [x] = x-1。以下は私のPRの定義であり、時間、AND、OR、NOT、pow、true、false、iteなどの他のいくつかの関数が定義されています。私がここに持っているものだけで減算を定義することは可能ですか？もしそうなら、誰かが私にいくつかのガイダンスを与えることができます。私の現在の考えは、minus[x,y]再帰y時間を与えてから戻ると、次のようなことができるということですP 2。y > xゼロを返す必要がある場合。以下は私のPRの定義です。

編集; 私の問題は、正しいベースケースを定義することにあることがわかりました。は正しい方向への一歩ですが、何度も繰り返す必要がありPR (P 3) (P 1)ます。私は何かがそれをするだろうと思っています。もちろんそれは正しくありませんが、アイデアは毎回デクリメントしてからに再帰することです。P 1 - 1P 3PR (PR Z (P 3)) (P 1)P 3ZP 1

If Then Else の定義のプロジェクションに問題があります。実際には If-Else-Then として実行されています。

スワップしようとするP 3と、P 4完全に壊れます（毎回「then」値を返します）。ite[0,2,3]戻る必要があり、戻る必要が3あります。代わりに、反対のことが起こっています。どうすればこれを修正できますか?ite[1,2,3]2