ステートマシンを理解する

コンピュータサイエンスの概念の紹介

コンピュータサイエンスはプログラミングを可能にしますが、基礎となるコンピュータサイエンスの概念を理解していなくても、多くのプログラミングを行うことができます。

これは必ずしも悪いことではありません。私たちがプログラムするとき、私たちははるかに高いレベルの抽象化で働きます。

私たちが車を運転するとき、私たちは2つまたは3つのペダル、ギアシフト、およびステアリングホイールだけに関心があります。あなたはそれがどのように機能するかについて明確な考えを持っていなくても安全に車を操作することができます。

しかし、その能力の限界で車を運転したいのであれば、3つのペダル、ギアシフト、ステアリングホイールだけでなく、自動車についてもっと多くのことを知る必要があります。

同じことがプログラミングにも当てはまります。コンピュータサイエンスをほとんど、またはまったく理解していなくても、日常業務の多くを達成できます。PHPで「お問い合わせ」フォームを作成するために、計算理論を理解する必要はありません。

ただし、本格的な計算を必要とするコードを作成する場合は、内部で計算がどのように機能するかについてもう少し理解する必要があります。

この記事の目的は、計算の基本的な背景を提供することです。興味があれば、さらに高度なトピックをフォローアップすることもできますが、今は、最も単純な抽象的な計算デバイスの1つである有限状態マシンの背後にあるロジックを調べたいと思います。

有限状態機械

有限状態マシンは、アルゴリズムの設計に使用される数学的抽象化です。

簡単に言うと、ステートマシンは一連の入力を読み取ります。入力を読み取ると、別の状態に切り替わります。各状態は、特定の入力に対してどの状態に切り替えるかを指定します。これは複雑に聞こえますが、非常に単純です。

長い紙を読み取るデバイスを想像してみてください。紙の1インチごとに、「a」または「b」のいずれかの1文字が印刷されています。

ステートマシンが各文字を読み取ると、状態が変化します。これは非常に単純なステートマシンです。

円は、マシンが存在できる「状態」です。矢印は遷移です。したがって、状態sにあり、「a」を読み取ると、状態qに移行します。'b'を読み取ると、状態sに留まります。

したがって、sから始めて、上紙テープを左から右に読むと、「a」を読んで状態qに移動します。

次に、「b」を読み取り、状態sに戻ります。

別の「b」はsを維持し、その後に「a」が続きます。これにより、q状態に戻ります。簡単ですが、ポイントは何ですか?

さて、最終的な状態を調べることで、ステートマシンにテープを実行し、文字のシーケンスについて何かを伝えることができることがわかりました。

上記の単純なステートマシンでは、状態sで終了する場合、テープは文字「b」で終了する必要があります。状態qで終了する場合、テープは文字「a」で終了します。

これは無意味に聞こえるかもしれませんが、このタイプのアプローチで解決できる問題は非常にたくさんあります。非常に簡単な例は、HTMLのページに次の順序でこれらのタグが含まれているかどうかを判断することです。

ステートマシンは、htmlタグを読み取ったことを示す状態に移行したり、headタグに到達するまでループしたり、headcloseタグに到達するまでループしたりすることができます。

最終状態に正常に到達した場合は、それらの特定のタグが正しい順序になっています。

有限状態マシンは、パーキングメーター、ポップマシン、自動ガスポンプ、その他のあらゆる種類のメカニズムなど、他の多くのシステムを表すためにも使用できます。

決定性有限状態機械

これまで見てきたステートマシンはすべて決定性ステートマシンです。どの状態からでも、許可された入力に対して遷移は1つだけです。言い換えれば、文字「a」を読んだときに、状態から抜け出す2つのパスが存在することはできません。最初は、これを区別するのはばかげているように聞こえます。

同じ入力が複数の状態に移行する可能性がある場合、一連の決定はどのようなメリットがありますか?コンピューターに伝えてif x == trueから実行しdoSomethingBigたり実行したりすることdoSomethingSmallはできませんね。

ええと、ステートマシンでできるのです。

ステートマシンの出力は、その最終状態です。これは、すべての処理を通過した後、最終状態が読み取られ、その後、アクションが実行されます。ステートマシンはしないそれは状態への状態から移動する何かを。

それは処理し、それが終了すると、状態が読み取られ、外部の何かが目的のアクションをトリガーします(たとえば、ソーダ缶を分配する)。これは、非決定性有限状態マシンに関しては重要な概念です。

非決定性有限状態マシン

非決定性有限状態マシンは、特定の状態からの特定の入力が複数の異なる状態につながる可能性がある有限状態マシンです。

たとえば、次のような文字列を認識できる有限状態マシンを構築するとします。

  • 文字「a」で始まります
  • その後、文字「b」が0回以上出現します。
  • または、文字「c」が0回以上出現する
  • アルファベットの次の文字で終了します。

有効な文字列は次のとおりです。

  • abbbbbbbbbc
  • abbbc
  • acccd
  • acccccd
  • ac(bの発生ゼロ)
  • ad(cの発生ゼロ)

したがって、文字「a」の後に「b」または「c」の同じ文字が0個以上続き、その後にアルファベットの次の文字が続くことを認識します。

これを表す非常に簡単な方法は、次のようなステートマシンを使用することです。ここで、tの最終状態は、文字列が受け入れられ、パターンに一致することを意味します。

問題がありますか?開始点sから、どのパスを取るべきかわかりません。文字「a」を読んだ場合、状態qまたはrのどちらに進むかわかりません

この問題を解決する方法はいくつかあります。1つはバックトラックによるものです。考えられるすべてのパスをたどり、行き詰まったパスを無視するか、元に戻します。

これは基本的にほとんどのチェスプレイコンピュータの仕組みです。彼らはすべての可能性、そしてそれらの可能性のすべての可能性を見て、相手に対して最大の数の利点を与える道を選びます。

もう1つのオプションは、非決定性マシンを決定性マシンに変換することです。

非決定性マシンの興味深い属性の1つは、非決定性マシンを決定性マシンに変換するアルゴリズムが存在することです。ただし、多くの場合、はるかに複雑です。

幸いなことに、上記の例は少しだけ複雑です。実際、これは非常に単純なので、正式なアルゴリズムを使用しなくても、頭の中で決定論的なマシンに変換できます。

以下のマシンは、上記の非決定性マシンの決定論的バージョンです。以下のマシンでは、マシンが受け入れる任意の文字列がtまたはvの最終状態に到達します。

非決定論的モデルには、4つの状態と6つの遷移があります。決定論的モデルには、6つの状態、10の遷移、および2つの可能な最終状態があります。

それだけではありませんが、通常、複雑さは指数関数的に増大します。適度なサイズの非決定性マシンは、絶対に巨大な決定性マシンを生成できます。

正規表現

何らかのプログラミングを行ったことがある場合は、おそらく正規表現に遭遇したことがあります。正規表現と有限状態マシンは機能的に同等です。正規表現を受け入れたり一致させたりできるものはすべて、ステートマシンを受け入れたり一致させたりすることができます。

たとえば、上記のパターンは正規表現と一致させることができます。 a(b*c|c*d)

正規表現と有限状態マシンにも同じ制限があります。特に、どちらも有限のメモリで処理できるパターンにのみ一致または受け入れることができます。

では、どのような種類のパターンが一致しないのでしょうか。'a'と 'b'の文字列のみを照合するとします。ここで、 'a'の数とそれに続く 'b'の数があります。またはN「に続いていますnはBの」ここでnはいくつかの数です。

例は次のとおりです。

  • ab
  • aabb
  • aaaaaabbbbbb
  • aaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbb

最初は、これは有限状態マシンにとって簡単な仕事のように見えます。問題は、状態がすぐに不足するか、無限の数の状態を想定する必要があることです。その時点で、それはもはや有限状態マシンではありません。

最大20個のaとそれに続く20個のbを受け入れることができる有限状態マシンを作成するとします。21'aの後に21'bの文字列が続くまで、これは問題なく機能します。その時点で、より長い文字列を処理するようにマシンを書き直す必要があります。

認識できる文字列については、メモリが不足しているためにマシンが認識できない文字列が少し長くなっています。

これは、基本的に「パターンに上記のように繰り返すことができるセクションがある場合、パターンは規則的ではありません」と言うポンピング補題として知られています。

言い換えると、パターンに一致するすべての文字列を認識する正規表現も有限状態マシンも構築できません

注意深く見ると、すべての「a」に一致する「b」があるこのタイプのパターンは、HTMLに非常によく似ていることがわかります。タグの任意のペア内に、他の一致するタグのペアをいくつでも持つことができます。

したがって、正規表現または有限状態マシンを使用して、HTMLのページに;があるかどうかを認識できる場合があります。と要素が正しい順序である場合、HTMLは正規パターンではないため、正規表現を使用してHTMLページ全体が有効かどうかを判断することはできません。ml>, ead>

チューリングマシン

では、不規則なパターンをどのように認識しますか?

チューリングマシンと呼ばれる、ステートマシンに似た理論上のデバイスがあります。それはそれが読む紙片を持っているという点で有限状態機械に似ています。ただし、チューリングマシンは、紙テープを消去して書き込むことができます。

チューリングマシンの説明には、ここにあるより多くのスペースが必要ですが、有限状態マシンと正規表現の説明に関連するいくつかの重要なポイントがあります。

チューリングマシンは計算上完全です。つまり、計算できるものはすべてチューリングマシンで計算できます。

チューリングマシンは紙テープからの書き込みと読み取りができるため、状態の数に制限はありません。紙テープの長さは無限大と見なすことができます。もちろん、実際のコンピュータには無限のメモリ容量はありません。ただし、通常は十分なメモリが含まれているため、処理する問題の種類の制限に達することはありません。

チューリングマシンは、計算プロセスがどのように機能するかを視覚化して理解できる架空の機械装置を提供します。これは、計算の限界を理解するのに特に役立ちます。興味があれば、将来チューリングマシンについて別の記事を書くつもりです。

なぜこれが重要なのですか?

それで、ポイントは何ですか?これは、次のPHPフォームの作成にどのように役立ちますか?

それらの制限に関係なく、ステートマシンはコンピューティングの非常に中心的な概念です。特に、設計できる非決定性ステートマシンには、同じことを行う決定性ステートマシンが存在することが重要です。

これは重要なポイントです。これは、最も考えやすい方法でアルゴリズムを設計できることを意味します。実用的なアルゴリズムができたら、それを最も効率的な形式に変換できます。

有限状態マシンと正規表現が機能的に同等であるという理解は、特にシステムを再コンパイルせずに変更できるビジネスルールの作成に関して、正規表現エンジンの非常に興味深い用途を開きます。

コンピュータサイエンスの基礎により、解決方法と理由がわからない問題を解決できます。「Xを解決する方法はわかりませんが、Yを解決する方法は知っています。そしてソリューションを変換する方法も知っています。 YをXの解に変換します。したがって、Xを解く方法がわかりました。」

この記事が気に入ったら、ソフトウェア作成のいくつかの側面について時折ビデオや漫画を作成する私のYouTubeチャンネルをお楽しみください。また、何か新しいものを作成するときに時々メールを送りたい人のためのメーリングリストもあります。

2018年2月11日にblog.markshead.comで最初に公開されました。