Games worth discovering

有限状態オートマトンの課題

Want

オートマトンは、電源を入れると人間の介入なしに次のような特定の質問に答える機械です。 1. a + b = c か? 2. 文字列に「a」が含まれていますか? 3. 「コーヒーを飲みに行こうかな」は「あなたに夢中です」という意味ですか? (この質問のオートマトンは設計されていないと思います。) このゲームでは、最も単純なオートマトンモデルである有限状態オートマトンを使用して、40 の課題に対処します。文字列の操作、2進数、日常生活などから生じます。このゲームにはすぐに始めるためのチュートリアルが含まれているため、有限状態オートマトンに詳しくなくても心配する必要はありません。また、次の概要を読み、オンラインで有限状態オートマトンを検索して、それに慣れることもできます。有限状態オートマトン有限状態オートマトン (FSA) は、最も単純なオートマトンタイプです。有限状態オートマトンは、いくつかの状態と遷移ルールで構成されます。遷移ルールは、状態がいつ別の状態に遷移するかを記述します。つまり、地下鉄の地図のように見えます。有限オートマトンのクライアントは文字列です。どの文字列が受け入れられ、どの文字列が拒否されるかを決定します。たとえば、FSA は有効な電子メール、電話番号などを受け入れることができます。次に、最初の例を見てみましょう。これには 2 つの状態があります。左側の状態「1」と右側の状態「2」です。緑色でマークされた「1」は、オートマトンがここから始まることを意味します。青色でマークされた「2」は、オートマトンがここで停止し、文字列の順序ですべての文字を読み取る場合にのみ入力文字列を受け入れることを意味します。したがって、このオートマトンは「a」を受け入れ、その他の文字列を拒否します。質問: 「ab」を受け入れる FSA と、「a」または「b」(略語、「a|b」) を受け入れる FSA を独自に設計してみてください (これらはゲーム内の 2 つの課題です)。非決定的 FSA (および他のタイプのオートマトン) の最も重要な概念は、非決定的と呼ばれます。この概念を紹介するために、オートマトンの 2 番目の例を示します。「b」で終わるすべての文字列 (「a」と「b」のみで構成される) を受け入れます。頭の中で「b」に対してこのオートマトンを実行します: (1) 「1」から始まり、「」の自己ループを実行します。 1" の場合、"b" をすべて読み取り、"1" で停止するため、"b" を拒否します。 (2) 「1」から始まり「2」に遷移し、「b」をすべて読み込むとともに「2」で停止するので、「b」を受け入れます。非決定性有限状態オートマトン (NFA) は、少なくとも 1 つのトレースが青色でマークされた状態で終了する場合、文字列を受け入れます。このオートマトンを頭の中で「ab」に対して実行します: (1) 「1」から開始し、「1」の自己ループを 2 回実行し、「ab」をすべて読み取り、「1」で停止するため、拒否します。「アブ」; (2) 「1」からスタートし、「1」の自己ループを1回実行して「2」に遷移し、「b」をすべて読み込んで「2」で停止するので、「ab」を受け入れます。非決定性が不可欠なのは、FSA が推測できるため、(私たち人間は推測することが好きなので) 自然かつ迅速にオートマトンを設計できるためです。有限状態オートマトンのいくつかのアプリケーション有限状態オートマトンを学習すると、コンピュータサイエンスの世界に入るのに役立ちます。また、次のような多くのアプリケーションを構築することもできます。 NPC (ノンプレイヤーキャラクター) の実装。ユーザーエクスペリエンスを向上させるために、多くのゲームには固定ロジックを繰り返す NPC が含まれています。たとえば、セールスマンが西から東へ、次に東から西へ移動し、本物のプレイヤーに近づいたら何かを買ってもらうように頼みます。ロジックは非常にシンプルなので、FSA はそれを実装できます。汎用プログラミング言語 (C や JAVA など) ではなく FSA を使用する利点は、FSA の方が読みやすく、テスト、変更、保守にかかる人的リソースのコストが少ないことです。

Additional information

会社

Tramolly Game

更新時間

03/19/2024