問題タブ [automata-theory]

チューリングマシンや有限状態オートマトンのような抽象マシンを実装するプログラミング言語を知っていますか?

つまり、次の入力を処理します。

• 5 タプル (形式言語 101 の悪名高い ⟨Q,Σ,δ,q0,F⟩ )、チューリング マシンまたは抽象マシンのその他の形式表現の7 タプル。
• 入力単語。

そして、入力された単語が受け入れ単語かどうかを教えてください。

ありがとう、

アダム

私は、意図的に (設計により) 同じコードを 2 回評価できない (つまり、ループできない) 専用の「プログラミング言語」を作成しました。基本的に、フローチャートの各要素が同じデータセットに対して異なるテストを実行する条件である、フローチャートのようなプロセスを説明するために作られています (変更することはできません)。ブランチは分割およびマージできますが、循環することはありません。フローチャートはそれ自体にループバックできません。分岐の最後に到達すると、現在の状態が返され、プログラムが終了します。

書き留めると、典型的なプログラムは表面的には純粋関数型言語のプログラムに似ていますが、再帰の形式が許可されておらず、関数が何も返すことができないという点が異なります。関数を終了する唯一の方法は、別の関数を呼び出すか、現在の状態を返す一般的な exit ステートメントを呼び出すことです。同様の効果は、構造化プログラミング言語を使用してすべてのループ ステートメントを削除するか、「非構造化」プログラミング言語を使用して、コード内で逆方向に進む goto または jmp ステートメントを禁止することによっても実現できます。

ここで私の質問は次のとおりです。そのような言語を簡潔かつ正確に説明する方法はありますか? 私は正式な CS のバックグラウンドがなく、オートマトン理論や形式言語理論に関する記事を理解するのが難しいので、少し途方に暮れています。私は自分の言語がチューリング完全ではないことを知っており、苦労して、自分の言語がおそらく「通常の言語」(つまり、読み取り専用のチューリング マシンによって評価できる言語) として分類できることを確信することができました。もっと具体的な用語はありますか？

一般的なプログラミングの概念に精通しているが、正式な CS のバックグラウンドを持っていない聴衆にとって、用語が直感的に理解できる場合はボーナス ポイントです。また、そのような言語を評価する特定の種類の機械または自動機械があれば、ボーナス ポイントも得られます。そうそう、データ ストリームを評価しているわけではないことに注意してください。すべての要素は、入力データの完全なセットに (読み取り専用で) アクセスできます。:)

私はオートマトン理論に関する本を読んでいます。この本は、0 と 1 の数が等しい言語が 1*0* と交差すると 1n0n になるという例を示しています。ここで、n > 0 です。

私の質問は、1*0* と交差したときに 1n0n になる正規言語を見つけるにはどうすればよいかということです。それを考える方法はありますか？

更新：答えてくれてありがとう！私が見つけようとしているのは正規の言語だと思うので、1n0n のような言語は機能しません ;) 可能ですか? 何か案は？

私はいくつかのテスト準備資料に取り組んでいて、この問題に固執しています。

L = {we {a、b} *：w = wRであり、すべてのaの直後にab}がある場合の文脈自由文法を表示します。

wRは逆にwです。したがって、英語では、すべての「a」の後に「b」が続く回文で、任意の数のaとbを使用します。

これまでのところ、逆の部分でこれを取得しましたが、回文のプロパティが保持されていることを確認しながら、すべてのaの後にabの部分を組み込む方法がわかりません。

どんな助けでも大歓迎です！

これが正しいフォーラムであるかどうかはよくわかりませんが、理論計算機科学でここに移動することが提案されました...

有限状態機械の典型的なアルファベットのサイズはどれくらいですか？

私は現在、高性能FAライブラリの実装に忙しく、続行する前にいくつかの設計上の考慮事項を検討する必要があります。私の状態空間は2147483 647（Integer.MAX_VALUE）のオーダーになります。これは、一般的でない使用でも十分すぎると思います。さて、残っているのはアルファベットスペースだけです。

アルファベットは通常、表示可能なすべての文字のみで構成されていると想定することにメリットはありますか（この場合、アルファベットをとして保存できるbyteため、非常に優れたパフォーマンスが得られます）。Stringまたは、アルファベットラベルを使用できるように、アルファベット記号をsに変換する必要がありますか？この場合、作成するサイズに応じて、を、またはStringのいずれかに変換するマップを保持する必要があります。intshortbyte

LTL（線形時相論理）に慣れていない場合は、この質問をスキップしてください。もちろん、LTLはプログラミングにとって非常に重要です。これは、プログラムの検証に使用するモデル検査システムの中核であるためです。

これらの命題記号とその意味を考えると...
Gp-常に
PFp-時々P

次のステートメントはどういう意味ですか？

私はLTLを取り巻くロジックに苦労しており、上記のステートメントに頭を悩ませることはできません。助けてくれてありがとう！

LBA（線形有界オートマトン）を勉強しています。いくつかの演習を解決する方法を理解しようとしています。

そこで、状況依存文法を与えられた LBA を簡単に作成する方法があるのだろうかと思います。

これは、LR 文法から DFA (決定論的有限オートマトン) に移行する方法のようなものです。

前もって感謝します

特定のアルファベットにいくつの異なる遷移グラフがあるかをどのように判断しますか? たとえば、アルファベット {x, y} を超える TG の数。Daniel IA Cohen の著書「Introduction to computer theory」からの同様の質問のクラスを受講しています。TG を作成する方法の例はたくさんありますが、言語ごとに作成できる数を決定するものはありません。限られた量のTGを探していると思いますか？どうもありがとうございます！

オートマトン理論クラスの宿題に取り組んでいます。これまでのところ、正規表現を含む単なる証明であり、それほどクレイジーではありません。とにかく、私の質問は、これは連結のための適切なセット表記法は何ですか? たとえば、R + S が R union S と同じであることはわかっていますが、私の人生では、連結に相当する集合論が何であるかを思い出せません。

私は問題に取り組んでいると思うので、問題を投稿するつもりはありません.誰かが私に正しい方向に少し突っ込んでもらえますか?

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

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