7月 6, 2020
Articles
コメントはまだありません

オートマトン理論はどのくらい実用的ですか？

理論計算機科学に関連するトピックに適用する方法は常にあります。しかし、教科書や学部課程では通常、オートマトン理論が重要なトピックである理由や、それがまだ実践されているかどうかについては説明されていません。したがって、学部生はオートマトン理論の重要性を理解するのに苦労し、実用的ではないと考えるかもしれません。

オートマトン理論はまだ実際に役立ちますか？

それは学部のCSカリキュラムの一部である必要がありますか？

コメント

  • これはここではトピックから外れていると思います。よくある質問をご覧ください。
  • 私は’ off = topic ‘-これの本質。’は明らかに研究レベルではありません、しかし、オートマトン理論の関連性に関するこの特定の質問は、頻繁に出てくる質問です。
  • これは完全に話題になっていると思います。有限オートマトン理論のアプリケーションは何ですか？頂点カバーアプリケーション実世界の陽イオンであり、’その質問を閉じませんでした。
  • ちなみに、この質問は密接に関連しており、その回答は有限オートマトン理論の研究にも実用的な動機を与える可能性があります：” 正規表現は何に適していますか？ “。
  • 回答の質と多様性により、”スコープ”の問題は関係ありません。すでに3票の賛成票があり、この質問が’端を越えないことを願っています。

回答

  1. grep / awk / sedのようなツールを使用したことがありますか？正規表現はこれらのツールの中心を形成します。

  2. 電子メールのような「実用的なプロジェクト」では、正規表現を原則的に使用することで、どれだけのコーディングを回避できるかに驚かれることでしょう。サーバー。

  3. CS専攻の場合は、間違いなく（少なくとも小さな）言語用のコンパイラー/インタープリターを作成することになります。このタスクの前に行き詰まったら、少しの理論（別名コンテキストフリー文法）がどれだけ役立つかを理解できます。この理論は、かつては不可能だったタスクを週末に完了することができるものにしました（そしてそれは発明者を獲得しました）チューリング賞-googleBNF）。

  4. CS専攻の場合、ある時点で、座ってコンピューティングの哲学的基盤について考える必要があります。 AndroidAPIの次のバージョンがどれほどクールか。ちなみに、大学の仕事は、人生の次の5年間に備えるのではなく、次の50年間に備えることです。この点で彼らができることは、考える手助けをすることだけです。それらのコースの1つとしてのオートマトン理論の例。

回答

より実用的な表現の1つCSのはコンパイラ構築です。 1965年、クヌースはLRパーサーの研究を開始しました。迅速に（10年以内に）、シフト/リデュースパーサーの実装を可能にする決定性プッシュダウンオートマトンのサブセットであるLALRパーサーがありました。

LALR解析の実現可能性と効率の中心は言語の「接頭辞」が規則的であることが判明したことの証明（Knuthによる）（有限オートマトン）。これは、yacc / bisonなどの自動パーサジェネレータの起源です。

私たちが知っているプログラミング言語は、これらの開発によるコンパイル効率の多くを負っていると言っても過言ではありません。

別の例を次に示します。TCP/ IPプロトコルの中心は有限状態マシンです。どれだけ実用的になることができますか？

すべての真面目なCS学生、特に実用的な学生は、オートマトン理論に注意を払う必要があります。これは、コンピュータサイエンスの豊かさの多くの基礎です。

コメント

  • ソースファイルの解析は、コンパイラの興味深い（そして重要な）部分ではないため、’ “プログラミング言語は、これらの開発によるコンパイル効率の多くを負っていると知っているので、安全だとは思いません”。さらに、PEGやパーセクの解析などのさまざまなツールを使用して言語を解析することもできます。

回答

そのノイズが聞こえますか？それは、オートマトン理論の天国で笑っている千の素晴らしい定理、アプリケーション、ツールの音です。

言語とオートマトンは、コンピュータサイエンスのあらゆる分野で見られる、エレガントで堅牢な概念です。言語は、先史時代の計算からの乾いた、形式主義的な受け継がれではありません。言語理論の観点では、洗練された不透明なオブジェクトに関する一見複雑な質問を、単語や木に関する単純なステートメントに抽出します。形式言語は、代数的位相幾何学によって古典的な数学にもたらされる基本的でゲームを変える視点に似たコンピュータサイエンスの役割を果たします。ここに、言語理論を介してアプローチされるいくつかの実用的でかなり複雑な実用的な問題があります。

  1. ドキュメント内のフレーズの重複オカレンスを見つけて、2番目のオカレンスを削除したいとします。本質的に、言語のシーケンスを置き換えたいと思います。
  2. プログラムにアサーション違反が含まれていますか？デバイスドライバーは、カーネルと対話するときに特定のプロトコルを尊重しますか？プログラムの動作は一連の実行です。言い換えれば、言語。正しさのプロパティは別の言語です。プログラムの正当性の問題は、言語の包含チェックに相当します。
  3. ソフトウェアが無限ループに陥ることはありますか？分散アルゴリズムにはライブロックが含まれていますか？無限の単語よりも言語が必要ですが、言語の包含ビューは引き続き適用されます。
  4. Webアプリケーションに入力された悪意のあるJavascriptを検出するサニタイザーを構築したいと考えています。悪意のある文字列のセットは言語です。別の言語でフォームに入力された文字列のセット。これらの言語の共通部分が空でないかどうかを判断する必要があります。
  5. 事後対応型およびミッションクリティカルなシステムの実行時監視。化学プロセスの操作を監視したり、財務データベースの更新を追跡したりするソフトウェアモニターを設計したいと考えています。これらは、本質的に言語の包含と交差の問題です。
  6. その多数のアプリケーションによるパターン認識。一連のバグレポートで、ゲノムデータ、テキスト、パターンのパターンを検出する必要があります。これらは、未知の言語から単語が与えられ、その言語を推測しなければならない問題です。これらは言語推論の問題です。
  7. 一連のXMLドキュメントが与えられた場合、これらのドキュメントに適用されるスキーマをリバースエンジニアリングする必要があります。 XMLドキュメントはツリーとして理想化できます。その場合、スキーマはツリー言語の仕様であり、スキーマ推論の問題はツリー言語に対する言語推論の問題です。
  8. 多くのアプリケーションでは、自動算術推論が必要です。プレスバーガー算術などの論理理論を修正するとします。この理論では、自然数、加算、および未満の述語があります。 n個の変数を持つ式は、n次元ベクトルのセットを表します。ベクトルは数字のシーケンスであり、単語としてエンコードできます。その場合、述語は単語のセットです。言語。結合、論理和、否定などの論理演算は、言語の共通部分、和集合、および補集合になります（存在記号は一種の射影です）。

上記の削減は、言語を抽象的な数学的対象として扱います。これらのアイデアを実際に適用するには、これらのデータ構造を操作するための言語とアルゴリズムを表すデータ構造が必要です。

オートマトンを入力します。 Automataを使用すると、言語などの抽象的な数学的オブジェクトに関する質問を、ラベル付きグラフに関する具体的なアルゴリズムの質問に減らすことができます。言語とオートマトン理論は、非常に多くの実用的なアプリケーションに加えて、非常に重要な知的サービスを提供します。郵便番号のフォーマットから、統一された整頓された概念空間でのモナディック2次論理の決定手順に至るまでの問題について考えることができます。なんて素晴らしいことでしょう！

私は論理と決定手順について何も言いませんでした。 （はい、実用的なアプリケーションがあります。）信頼できる概要については、Kavehの回答を参照してください。

コメント

  • 皮肉なことに、

回答

他の回答で説明したように、オートマトン理論は、私たちがよく理解している単純な計算モデルとして概念的に重要です。正規表現とオートマトンには多くの実際のアプリケーションがあります。

これは、オートマトン理論に戻って現代の概念を理解する現代の研究の小さな例です。この論文で研究者は、正規言語にはすべてプロパティテスターがあることを証明しています。「正規言語は一定数のクエリでテスト可能です」

回答

これは単なるバニラオートマトンではありません。あなたは（計算）の基本（状態の受け入れ、イプシロン遷移など）について学習しています。何ができるか、さらに重要なことに、いくつかのクエリ言語で何が表現できないかについて推論するのに役立つモデル。いくつかの興味深い結果は次のとおりです。

（そしてもちろん私はたくさんスキップしています他のクラスの）

基本的に、それは非常に一般的なモデルです。あなたのクラスはおそらくオートマトン、言語、論理の間のリンクを強調するでしょう。

これを具体的な「世俗的な」ツールに関連付けることを検討している場合は、図書館でのんびりと朝を過ごし、 Foundations of Databases by Abiteboul & al、そしてこれをクラスの資料に接続しようとしています。もちろん、それはただのオートマトンクラスのアプリケーションを探す（多くの）方法の1つであり、最も明白ではないと思いますが、それが興味深い演習である理由です。

回答

さまざまな回答ですでに指摘されているように、UGコースのオートマトン理論は、より高度な（そして実用的な）トピックを導入するための基本的な概念フレームワークを提供します。見落とされた接続を指摘するため。例：二分決定性図（DFAは最小化されています。DFAを教えた後、BDDベースのパズル解決を教えることがよくあります）。 BioPerlおよびBioPythonに含まれるスクリプティング（および実際のスクリプト正規表現に隠されている可能性のある意図しない一致の数を強化するための優れた設定）、正式なデバッグ（否定されたFA、交差などの状態プロパティ）、さらにはVCRまたはホーム侵入者アラームプログラミング（不完全な例で教えられた、指定が不十分なオートマトンの毎日のストレス状況。おそらく、Harelのプレイイン/プレイアウトシナリオベースのユーザーインターフェイスの合成を使用して形式化されています。）また、この設定を使用して、Pythonを（ほぼ）純粋に教えています。マップ、ラムダ、セット内包表記などの機能サブセット。これを使用して、標準のFAアルゴリズムを、多くの場合、数学の定義と実質的に区別できない方法でコーディングできます。

コメント

  • ようこそ、ガネーシュ！
  • オートマトンを教える良い方法です。講義ノートを共有してもよろしいですか？

回答

オートマトン理論に関連するかなりの研究があります。業界で使用されるモデル検査で。 フィールドインスティテュートでのMosheVardiの最近の講義、特に3番目の講義「論理、オートマトン、ゲーム、およびアルゴリズム」で、オートマトン理論がなぜであるかを確認してください。

要約：

Buechi、Elgot、Rabin、および1950年代と1960年代のトラクテンブロットは、決定手順の最も基本的なアプローチの1つです。最近、このアプローチは、ハードウェアおよびソフトウェアシステムの正式な検証に産業用アプリケーションを見つけました。論理から実用的なアルゴリズムへのパスは、オートマトンだけでなく、アルゴリズムの側面が1970年代後半にチャンドラ、コーゼン、ストックマイヤーによって研究されたゲームを通じて。この概要の講演では、オートマトンとゲームを介したロジックからアルゴリズムへのパスについて説明します。

講義のスライドとオーディオファイルは、 1 aから入手できます。 >、 2 、 3 。

回答

まったく異なる実用的な角度から別の答えを投げます：有限状態マシン（または少なくともそれらのいくつかの単純な一般化/拡張）がAIでよく使用されますゲームプログラミングの側面。それらは、キャラクターの振る舞いをカプセル化するための優れたモデルを提供することが判明しました。たとえば、敵は、「パトロール」、「検索」、「アプローチ」、「攻撃」、「防御」、「退却」、「死ぬ」などを表す状態を持ち、それらの間の遷移が明確に定義されている場合があります。これには、正規言語などのオートマトンの形式的な側面は含まれませんが、オートマトンの概念は非常に重要なものです。

回答

理論と実践を対比し、上下に設定する言語は非常に完成度が高いことがわかりました。無知の-それは人が思考の最初の要素に精通していないことを証明し、それらを教えることができないほどに彼の心が変質していることを証明するのに大いに役立ちます。

— James Mill（偽名で「PQ」）、「理論と実践」、ロンドンとウェストミンスターのレビュー、1836年4月

回答

「実用的」と「応用」という言葉の意味を考慮に入れる必要があります。一部の学生にとって、実用的は彼らが試験に合格するのに役立つものです。他の人にとっては、仕事で出てくるものは何でも。どちらの場合も、オートマタ理論は確かに非常に実用的です。

他の人が指摘しているように、たとえばコンパイラを勉強するときは文法を使用します。しかし、それだけではありません。たとえば、コードがあちこちで冗長であり、コードを改善すると、コードが冗長であることに気付いたときに、状態とそれらの間の遷移のルールが異なるという概念全体を理解することで、より優れたプログラマーになることができます。 DFA最小化の背後にある同じ概念的なアイデアをコードに適用しています。

「アプリケーション」についても同様です。その言葉で何がわかりますか？あなたが「現実的なエンジニア」であるとしても、実際のプロジェクトでオートマトン理論と同様のアイデアを見て、使用するでしょう。プログラミングコード、フロー図、さらにはシンプルでありながら素晴らしいスタックの概念です。私のような理論オタクの場合、論理、代数、有限モデル理論などの他の分野でのオートマトン理論のアプリケーションを検討します。確かに、スーパーマーケットで買い物をしているときに正規言語の反復補題を使用する必要はおそらくないでしょうが、そのような定理は構造は言うまでもなく、それらが対応する論理と代数構造です。そして、それは私が実用性のどの尺度よりも大切にしていることです。

回答

ロジックと一緒に投げられると、オートマタはオートマトン$ A $と式$ \ varphi $については、

$ \ qquad A \ models \ varphi $

のような政治家をチェックしてください。 $ A $がシステムのモデルであり、$ \ varphi $がシステム検証を取得する目的のプロパティの形式化である場合、実行可能なアプリケーションの数が増えることで非常に実用的な懸念事項になります。

物事の自動化の側面を考慮する素晴らしいアルゴリズムにつながります。たとえば、$ \ varphi $が LTL 式で$ A $がBüchiオートマトン（つまり、無限に実行される有限オートマトン）である場合、$ \ varphi $を変換できます。同等のオートマトン$ A_ \ varphi $に変換し、$ \ cal {L}（A）\ subseteq \ cal {L}（A_ \ varphi）$

回答

かどうかを確認します。

有限オートマトン。多くの場合、さまざまなコンテキストで有限状態マシンとして記述されているか、確率的バリアントとともに記述されています。隠れマルコフモデルは、パターン認識とパターンの構造の定量化に適用できます。例えば。与えられた確率分布に従って、またはある分布からの文字列（または時系列）のサンプルの統計的特性に一致する文字列を生成する最小の確率的有限オートマトンは何ですか。

たとえば、 CSSR を参照してください。これは、隠れた状態を盲目的に再構築するためのアルゴリズムです。隠れマルコフモデルよりも効率的で柔軟性があります。

コメント

  • 実用面に追加するために、隠れマルコフモデルは音声認識で使用されます。 Kurzweilなどのプログラム。

回答

オートマトン理論のもう1つのより実用的なアプリケーションは、人工知能の開発です。人工知能は有限オートマトンの概念から開発されました。ロボットのニューラルネットワークはオートマトン理論に基づいて構築されています。結局のところ、ロボットもオートマトンです。

回答

産業との関係については、優れた回答をしている人もいます。重要なのはその科学的価値であり、オートマタ理論は、計算理論の上位層を最初に理解するための入り口であることがよくあります。学部生の研究で。オートマトン理論には、理論計算機科学のいたるところに現れる一連の壮大な定理があります。特に、コンパイラなどのアプリケーションについて話したい場合はそうです。その科学的価値（時代遅れではない、どうしてそうなのか？それはこの分野の核となる理論です。）は、計算に興味のあるすべての科学者にとって実用的です。それは理解したり欲しい人にとって有用な知識であるため実用的です。計算の性質を理解するために。使用法が見つからない場合は、CSがプログラミングではなく（CSのアプリケーションである）、正式な科学であるため、CSを研究したり、研究する意図さえも疑問視します。

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です