問題タブ [automata]

BNF Grammar のルールを適用して、 a_Num の派生を生成したい

連想コンテナのキーとして有限オートマトンを使用できるようにする必要があるという問題があります。各キーは実際には同値類のオートマトンを表す必要があるため、検索すると、そのオートマトンが構造的に同一でなくても、同等のオートマトン（そのようなキーが存在する場合）が見つかります。

明らかな最後の手段のアプローチは、もちろん、チェックされた各キーの等価性テストで線形検索を使用することです。私はこれよりもはるかに良いことができることを望んでいます。

私は、任意であるが一貫した順序付けを課そうとし、順序付けされた比較アルゴリズムを導出するという観点から考えてきました。最初の原則には、オートマトンが表す文字列のセットが含まれます。各オートマトンの可能な最初のトークンのセットを評価し、それらの2つのセットに基づいて順序付けを適用します。必要に応じて、可能な2番目のトークン、3番目のトークンなどのセットに進みます。これを単純に行う場合の明らかな問題は、同等性を証明する前にチェックするトークンセットが無限にあることです。

私はいくつかの漠然としたアイデアを検討してきました-最初に入力オートマトンを最小化し、ある種のクロージャーアルゴリズムを使用するか、通常の文法に変換し直します。いくつかのアイデアはスパニングツリーを含みます。トークンのセットの辞書式順序を放棄する必要があるという結論に達しましたが、これまでに到達した最も重要な結論は、これは些細なことではないということです。他の誰かの解決策。

CiteSeerX（サブグループと剰余類の全順序付け）から論文をダウンロードしましたが、私の抽象代​​数は、これがまだ適切かどうかを知るのに十分ではありません。

また、オートマトンからハッシュを導出する方法があるかもしれないと思いましたが、私はまだこれほど多くのことを考えていません。

誰かが読むのに良い論文を提案できますか？-または、少なくとも私がダウンロードしたものが赤いニシンであるかどうかを知らせてください。

「形式言語とオートマタ理論」に関する良い本をいくつか提案してください。

ありがとう！

好奇心から、私が使用しているシステムがどの計算モデルと機能的に同等であるかを特定し、その同等性を証明しようとしています。この問題に時間を費やすほど、システムがチューリングと同等ではないことが疑われます。チューリング マシンと再帰的に列挙可能な言語についてはよく理解していますが、機能の少ないオートマトン (プッシュダウン オートマトンなど) についてはよく知らないので、どのように進めればよいかわかりません。

まず、さまざまな計算モデルについて学習するための優れたリソースを推奨できる人はいますか? 文法、言語、オートマトンに興味があり、それらすべての同等性と相違点を証明する方法に興味があります。理想的には、リソースは各モデルのすべての要素を詳細に分析し、それらを比較します。

第二に、システムをこれらの計算モデルのいずれかに当てはめようとするときに使用すべき一般的なアプローチまたはフレームワークはありますか?

目の前に問題があり、どのデザイン パターンを使用すればよいかわかりません。問題は次のようになります。

「N」個の状態を持つシステムを構築する必要があり、私のシステムは、いくつかの条件に応じて、任意の状態から他の状態に遷移する必要があります。例：条件1で状態1から3へ、条件2で状態1から4へ移動。

ある状態から別の状態への遷移でさえ、2 つ以上の異なる条件で実行できます。

たとえば、状態 1 から状態 3 への遷移は、次の場合に実行できます。
条件 1:「日曜日です」
条件 2:「雨が降っています」
条件 3:「雨と日曜日」
それぞれの条件で、状態 3 での処理は次のようになります。違う。

問題を読みやすく理解できたと思います。親切に助けてください。

どうもありがとう

アルゴリズムの擬似コードがすでにある場合、チューリングマシンが何をするかを説明するのに役立つガイドラインはありますか？

私は複雑さの理論のコースを受講しており、Cやアセンブリのようなものでコーディングする方法を知っていても、いくつかの言語（状態、遷移など）を決定または受け入れるチューリングマシンについて説明するのに時間がかかります。チューリングマシン（それに取り組んでいる）を十分に練習していないと思いますが、何か提案があればありがたいです。

編集

チューリングマシンのシミュレーターを作りたくありません。いくつかの言語を決定するために、紙にチューリングマシン（アルファベット、状態、遷移）を記述したいと思います。

これは、私が意味する簡単な例です。たとえば、0と1の文字列を調べ、その中のすべての0を1に変更するチューリングマシンを作成する必要があるとします。たとえば、テープ（入力）で11010から開始すると、テープ（出力）で11111で停止します。これで、高級言語では、次のようなものであることがわかります。

チューリングマシンの説明は、非公式に次のようなものです。

qとhaltの2つの状態があります。状態qにあり、1が表示されたら、変更せずに右に移動します。0が表示されている場合は、1に変更して、右に移動します。空白の記号（テープの終わり）が表示された場合は、停止状態になります。

正式には、状態に対して{q、halt}のようなものがあります。{（（q、1）->（q、1、R））、（（q、0）->（q、1、R））、（（q、＃）->（halt、0、L） ）}トランジションの場合。

現在、この問題は些細なことですが、より複雑な問題もあります（1進数を追加するか、a、b、およびcの数が等しい言語を認識します）。それらの擬似コードを簡単に書くことはできましたが、チューリングマシンを書くことははるかに困難であり（時間がかかります）、そのような問題をよりよく解決するのに役立つヒント、リソース、またはガイドラインがあるかどうか疑問に思いました。

チューリングマシンで処理できる言語とLBAで処理できない言語がありますが、LBAでは解決できないがTMでは解決できる有用で実用的な問題はありますか？

LBAは、有限のテープを備えたチューリングマシンであり、実際のコンピューターには有限のストレージがあるため、LBAで実行できない実用的な重要性は何もないように思われます。 線形拘束オートマトンには有限のテープだけでなく、入力のサイズの線形関数であるサイズのテープがあるという事実を除いて。有限性の線形性はLBAを何らかの方法で制限しますか？

LBAが対処できない問題はありますが、指数関数的に制限されたオートマトンは（そのようなものが存在する場合）可能ですか？

2つの言語に共通の文字列があるかどうかをテストしたいと思います。これらの言語は両方とも、以下で説明する正規言語のサブセットからのものであり、サンプルの文字列を生成するのではなく、両方の言語に文字列が存在するかどうかを知る必要があるだけです。

言語は、次のようなグロブのような文字列で指定されます

/foo/**/bar/*.baz

ここで、**0個以上の文字に*一致し、そうでない0個以上の文字に一致/し、他のすべての文字はリテラルです。

何か案は？

ありがとう、マイク

編集：

うまく機能しているように見えるものを実装しましたが、正当性の証明はまだ試していません。ソーステストと単体テストを見ることができます

次の言語を決定するための文法またはオートマトンを見つけるのを手伝ってください。

a ⁿ b ⁿ c ⁿここで、n≥1

(有向) グラフは、有限オートマトンを表します。これまで、私のテスト プログラムは、テスト用にドット ファイルを書き出していました。これは、回帰テスト (検証済みの出力ファイルを subversion に保持し、変更があったかどうかを確認する) と視覚化の両方に適しています。ただし、いくつかの問題があります...

基本的に、C++ から呼び出し可能で、状態と遷移のレイアウトを計画するが、描画は私に任せるものが必要です。つまり、好きなように描画して GUI (wxWidgets) ウィンドウに描画できるものです。

また、商用利用を許可するライセンスも必要です。現時点では必要ありません。オープン ソースとしてリリースすることも十分考えられますが、ATM のオプションを制限したくありません。

GraphViz の問題点は、(1) Windows でのソースからのビルドに関する警告、(2) レンダリングと解析のためのすべての不要な依存関係、(3) レイアウト専用の文書化された API の (推定) 欠如です。

基本的に、状態 (外接する四角形のサイズ) とトランジションを指定し、各トランジションの状態とウェイポイントの位置を読み取り、それらの座標に基づいて自分で描画できるようにしたいと考えています。トランジションの注釈をどのように処理する必要があるかはよくわかりませんが、それらの境界ボックスのサイズを指定し、それらをトランジションに関連付け、位置を読み取るための何らかの準備が必要です。

これらの要件を処理できるライブラリを知っている人はいますか?

私は必ずしも自分で何かを実装することに反対しているわけではありませんが、この場合、可能であれば避けたいと思います。