問題タブ [finite-automata]

それで、私は MIT の OpenCourseWare から Discrete Math コースを受講していますが、疑問に思っています...関係とグラフの関係はわかりますが、それを「所有」するには十分ではありません。私は単純なステート マシンを SQL にも実装したので、関係とセットがどのように完全に適用されるかについてのより厳密な研究ではなく、グラフをかなりよく理解しています。すぐには理解できないものをざっと見て、もっと学んだときに戻ってくるというYeggeの一連の思考に従うべきですか？日々作成しているグラフ構造をよりよく分析できるようになりたいと思っています (面白そうです)。また、今すぐ貴重な情報を逃さないようにしたいと思っています。

（編集：さまざまな集合と関係のプロパティがグラフ理論などにどのように関連しているか、および基本的なグラフ理論が集合/関係にどのように関連しているかについて、より良いアイデアを得たいと思います。）

これについてもっと学ぶことができる良いリソースはありますか? 重要な場合に備えて、Rosen の Discrete Mathematics and Its Applications の第 5 版を使用しています。

ありがとう！

Cで単純なステートマシンを実装する必要があります。
標準のswitchステートメントが最善の方法ですか？
現在の状態（状態）と遷移のトリガーがあります。

単純なステートマシンのためのより良い方法はありますか

編集：C ++の場合、 BoostStatechartライブラリが最適な方法だと思います。ただし、Cには役立ちません。Cのユースケースに集中しましょう。

未知の回数発生するネストされたパターンに一致する正規表現を書くことは可能ですか? たとえば、外側の中かっこ内に入れ子になっている開き/閉じ中かっこの数が不明な場合、正規表現は開き中かっこと閉じ中かっこを一致させることができますか?

例えば：

一致する必要があります:

感謝祭の後に学校に戻ったら、決定論的および非決定論的な有限状態マシン、チューリング マシン、プッシュダウン オートマトンなどのトピックを扱う CS 理論のコースを受講します。ただし、それらを視覚的に表現し、それらがどのように機能するか (合格/不合格など) をテストできる優れたアプリケーションは見つかりませんでした。私がこれまでに見つけた最高のものはjFlapですが、かなり扱いにくいと感じています。

使用されるほぼすべてのプログラミング言語はチューリング完全であり、これにより言語は計算可能なアルゴリズムを表すことができますが、独自の問題も伴います。私が書いているアルゴリズムはすべて停止することを意図しているため、停止することを保証する言語でそれらを表現できるようにしたいと考えています。

文字列と有限状態マシンの照合に使用される正規表現は、 lexingのときに使用されますが、チューリングが完全ではない、より一般的で幅広い言語があるかどうか疑問に思っています。

編集：明確にする必要があります。「汎用」により、必ずしもすべての停止アルゴリズムをその言語で記述できるようにしたいわけではありません（そのような言語が存在するとは思いません）が、共通のスレッドがあると思われますすべてのアルゴリズムが停止することが保証されている言語を生成するために一般化できる停止証明。

この問題に取り組む別の方法もあります - 理論的に無限のメモリの必要性を排除します。マシンが許可されるメモリの量を制限すると、マシンが存在する状態の数は有限であり、数えることができるため、アルゴリズムが停止するかどうかを判断できます (マシンが以前の状態に移行することを許可しないことによって)。 ）。

えーと-質問が言ったこと。それは私がよく耳にすることですが、私はまだそれを調査することに取り掛かっていません。

（更新）私は定義を調べることができました...しかし、なぜ（@eriksonによって指摘されたように）あなたの実際の経験と逸話への洞察を得ないのですか？コミュニティWikiは、人々が最も洞察に満ちた答えに投票するのに役立ちます。これまでのところ興味深い読書、ありがとう！

学習演習（およびブログ資料）としての正式な定義にできるだけ近いDFAを実装しています

セットが定義に含まれるjava.util.Setを使用することを計画しました。

定義には、正当な状態遷移を定義するためのタプルのセットが含まれます：（state、symbol）->nextState。

メンバーstate、symbol、nextStateを持つTransitionクラスがあります。状態とシンボルが一致する場合に2つの遷移が等しいことを示すために、equals（）とhashCode（）を実装しました。次に、遷移インスタンスのjava.util.Setがあります。

私の処理アルゴリズムでは、次のシンボルを読み取るときに現在の状態になります。これら2つを使用してTransitionオブジェクトを作成し、一致するTransitionをセットから引き出すことを期待していました。これにより、次の状態が通知され、反復できます。

しかし、-さらに使用するためにjava.util.Setのメンバーを抽出する方法がわかりません。remove（Object o）はできますが、ブール値を返すだけです。

私は何が間違っているのですか？

有限状態オートマトンを描くものを書きたいです。これに関連するアルゴリズムを知っている人はいますか?

編集:私はgraphvizについて知っていることに言及する必要があります。私は独自の描画プログラム/機能を構築したいので、探しているのは、アルゴリズムの理論的なもの/疑似コードです。

フロントエンドのウィジェット コードをスパゲッティ化する方法を探しています。私がやっていることを考えるには、有限状態マシンが正しい方法であることが示唆されています。私は、ステート マシンのパラダイムがほとんどすべての問題に適用できることを知っています。実際にこれを習慣化している経験豊富なUIプログラマーがいるのだろうか.

質問は、あなたの UI プログラマーの中で、あなたの仕事でステート マシンの観点から考えている人はいますか? もしそうなら、どのように？

ありがとう -モーガン