問題タブ [automata]

私はこれについてかなり長い間考えていますが、それでもそれについては遠くまで行くことができませんでした。最初のステップは、形式o ^ Mの言語を考えると簡単です。ここで、Mは、対戦相手が与えたものよりも大きい素数です（たとえばn）。ここから、対戦相手がどのようであっても、どのように証明できるかわかりません。文字列を壊して、文脈自由言語（したがって正規言語）のクラスに属していないことを示すために、いつでもそれをポンピングできます。

PS：宿題の質問ではありません。私はすでにこのコースを完了しています。コース期間中に解決できなかったので、解決しようとしています。

この言語が規則的かどうかを確認するタスクが与えられました。

これに対する正規表現も、決定論的 (またはそうでない) 有限状態オートマトンも見つかりません。一方、ポンピングの補題定理で逆を証明する方法は見つかりませんでした。

何か案は？

スタックサイズがたとえば20アイテムに制限されているPDAで受け入れられる言語のタイプは何ですか？

私の見解では、保存する一時的なメモリがあるため、CFLのままである必要があります。

私はある種のオートマトンの構成を行っています。そのため、より明確にするために、構成されたオートマトンを視覚化/描画したいと考えています。私はJavaでコーディングを行いました。したがって、誰でもこれに使用できるライブラリまたはツールを提案できます。これを行う方法がわかりませんか？

少し前に、私はセルオートマトンのような Wa-Tor を書きました (ウィキペディアを参照)。安定したシステムを得るために多くの微調整を行った以外は、非常にシンプルでうまく機能しました。しかし、それ以来、セルを「現実的に」更新する方法を自分自身 (そして今はあなた) に尋ねています。

私の「世界」はグリッドで、常に左上から右下に更新されていました。IMO は、上と左に近いセルが常に高速であることも意味します。たとえば、セル [3, 3] の魚は、更新される前に [3, 2] のサメに食べられる可能性があります。セルが反対の位置にある場合、魚は更新される前にサメから離れることができるため、常にサメから逃げます。

これは「問題」（または少なくとも非現実的）であるというのは正しいですか？

現実的な設定では、すべてのセルを同時に更新する必要がありますが、そのようなものを実装する方法がわかりません。私が想像できる別の方法は、「シャッフルされた」順序でセルを評価することです。

この問題をどのように解決しますか / そのような問題は通常どのように解決されますか?

上記のオートマトンの場合、私の教科書で与えられている正規表現は次のとおりです。

私はこれを導き出すのに苦労しています...以下はそれに対する私の試みです：

私は間違っているか、本に記載されている形式に単純化することができません。誰かが私をここに案内してくれたり、間違いを指摘したり、段階的に説明してくれませんか？

本当にありがたいです。

以前、私はここで、有限オートマトンの遷移グラフを正規表現に変換するための助けを求める質問をしました。

この有限オートマトンの正規表現を理解（および形成）する

ユーザーPatrick87のおかげで、探していたヘルプを見つけることができました。私はまた、彼が彼の答えで言及した次のリンクを読みました：

http://krchowdhary.com/toc/dfa-to-reg-exp.pdf

これは、正規表現を見つけるための3つのアルゴリズム手法を説明しています。直感的に、私はBrzozowski代数法に惹かれ、上部に記載されている前回の投稿で助けを求めていたFAを解決しようとしました。

以下は私がFAのために作った特性方程式です。私が間違っている場合は教えて訂正し、正しい方向に向けてください！

R1 = bR2 + aR3

R2 = aR2 + bR4

R3 = aR3 +bR2+λ

R4 = aR4 + bR3

これらは正しいですか？はいの場合、すべてのRiはRjに関してi≠jであるため、どのように置換を行うのですか。

助けてください：D

私はこれを理解したと思っていました...しかし、私はまだ頭を包み込むことができません。私はOpenFstで遊んでいて、「対数」セミリングで「最短距離」がどのように計算されるかを理解しようとしています。次の小さなオートマトンでは、

http://i.imgur.com/FThh6.png

「最短距離」コマンドの結果は、

ログの最短距離の説明は、次のように与えられます。

対数セミリングでは、q へのパスの重みの (対数) 合計が計算されます。

私はかなりばかげているように感じますが、最終的な -2.6 に到達するために実際に何が起こっているのか理解できません。対数合計と通常の合計の考えられるすべてのバリエーションを試してみましたが、適用すべきではないように思われるものも含めて、-2.6 は得られませんでした。今、私を夢中にさせ始めています。

この場合の私の直感は、2 つの異なる文字列 (bc、bd) のそれぞれの合計パス確率を合計してから、最良の確率を返す必要があるということです。(bc) には 2 つのパスがあり、それらの確率の合計は 2/3 (非対数) になります。(bd) パスの確率は 1/3 です。しかし、これは間違いなく起こっていることではないので、何が起こっているのでしょうか?

オートマトン正規表現と最小文字列長（int）を受け入れ、可能な文字列を生成できるようなプログラムをJavaで作成するにはどうすればよいですか？

正規表現の例は次のとおりです。

私は TA ですが、学生から次のような質問を受けました。恥ずかしいことに、私は答えを思いつくことができなかったので、皆さんに頼ります。

L_1 = {a^nb^nc^n} が非 CFL であることはわかっています。また、L_2 = {a^ib^kc^j : i != k }は文脈自由であることもわかっています。

それらの結合はどうですか？(明らかに不規則です) 文脈自由ですか？