by Mark Shead
An intro to Computer Science concepts
コンピュータ サイエンスによって私たちはプログラミングをすることができますが、基礎となるコンピュータ サイエンスのコンセプトを理解していなくても、多くのプログラミングを行うことができます。
これは必ずしも悪いことではありません。プログラミングでは、より高い抽象度で作業を行います。
私たちが車を運転するときに気にするのは、2つか3つのペダル、ギアシフト、そしてステアリングホイールだけです。
しかし、自動車を極限まで使いこなそうと思ったら、3つのペダル、ギアシフト、ハンドルだけではなく、もっとたくさんのことを知っていなければなりません。 日常の仕事の多くは、コンピュータサイエンスをほとんど、あるいはまったく理解していなくても成し遂げられます。
しかし、本格的な計算を必要とするコードを書こうと思ったら、ボンネットの中で計算がどのように機能しているかをもう少し理解する必要があります。
この記事の目的は、計算の基本的な背景を提供することです。
有限ステート マシン
有限ステート マシンは、アルゴリズムを設計するために使用される数学的な抽象化されたものです。 ある入力を読み取ると、異なる状態に切り替わります。 それぞれの状態は、与えられた入力に対して、どの状態に切り替えるかを指定します。
長い紙を読む装置を想像してみてください。 紙の1インチごとに、「a」または「b」の文字が1つ印刷されています。
ステートマシンが各文字を読み取ると、状態が変化します。
円は、機械が入ることのできる「状態」です。 矢印はその遷移を表しています。
つまり、sの状態からスタートして、上の紙テープを左から右に読むと、「a」を読んで状態qに移行します。
そして、「b」を読んで、状態sに戻ります。
さらに「b」を読むと、状態sにとどまり、「a」を読むと、状態qに戻ります。
さて、テープをステート マシンに通して、最終的にどの状態になるかを調べることで、文字の順序について何かを知ることができることがわかりました。
上の単純なステート マシンでは、状態 s で終わる場合、テープは文字 ‘b’ で終わらなければなりません。
これは無意味に聞こえるかもしれませんが、この種のアプローチで解決できる問題は非常に多くあります。
<html> <head> </head> <body> </body> </html>ステート マシンは、html タグを読み取ったことを示す状態に移動し、head タグに到達するまでループし、head close タグに到達するまでループし、……と続けます。
無限ステート マシンは、パーキング メーター、ポップ マシン、自動ガス ポンプの仕組みなど、他の多くのシステムを表現するためにも使用できます。
決定論的有限ステート マシン
これまで見てきたステート マシンは、すべて決定論的ステート マシンです。 どの状態からも、許可された入力に対しては 1 つの遷移しかありません。 言い換えれば、「a」という文字を読んだときに、ある状態から2つのパスがつながることはありません。
同じ入力が複数の状態に移行する可能性がある場合、一連の決定に何の意味があるのでしょうか。 コンピュータに、if x == true then execute doSomethingBig or execute doSomethingSmallと伝えることはできません。
しかし、ステート マシンではそのようなことができます。
ステートマシンの出力は、最終的な状態です。すべての処理を経て、最終的な状態が読み込まれ、アクションが実行されます。
ステートマシンは、状態から状態へと移行する間、何もしません。
処理を行い、最終的には、状態が読み込まれ、外部の何かが目的のアクション（例えば、ソーダ缶を出す）を引き起こします。 これは、非決定論的な有限状態マシンに関して重要な概念です。
非決定論的な有限状態マシン
非決定論的な有限状態マシンとは、特定の状態からの与えられた入力が、複数の異なる状態につながる可能性がある有限状態マシンのことです。
例えば、次のような文字列を認識できる有限状態機械を作りたいとします。
- 「a」で始まり、「b」の文字が0回以上続くか、「c」の文字が0回以上続き、「a」の次の文字で終わる。
有効な文字列は次のとおりです。
- abbbbbbbc
- abbbc
- acccd
- accccd
- ac（bの出現回数が0回）
- ad（cの出現回数が0回）
つまり、「a」の後に「b」または「c」の同じ文字が0回以上続くと認識されます。
このように、文字「a」の後に、「b」または「c」の同じ文字が0個以上続き、さらにその次のアルファベットを認識します。
これを表現する非常に簡単な方法は、以下のようなステート マシンで、最終的な状態が t であれば、文字列が受け入れられ、パターンに一致したことを意味します。
問題がわかりますか？ 出発点sから、どの道を行けばいいのかわかりません。
この問題を解決するには、いくつかの方法があります。 1つはバックトラックです。
これは基本的に、ほとんどのチェスをするコンピュータがどのように動作するかを示しています。
もう 1 つのオプションは、非決定論的なマシンを決定論的なマシンに変換することです。
非決定論的なマシンの興味深い特性の 1 つは、任意の非決定論的なマシンを決定論的なマシンに変換するアルゴリズムが存在することです。
幸いなことに、上の例はわずかに複雑なだけです。
下の機械は、上の非決定論的機械の決定論的バージョンです。
非決定論的モデルは、4つの状態と6つの遷移を持っています。
それほど多くはありませんが、複雑さは通常、指数関数的に増大します。
正規表現
何らかのプログラミングをしたことがある人なら、正規表現に遭遇したことがあるでしょう。 正規表現と有限状態機械は機能的に同等です。
たとえば、上述のパターンは、正規表現でマッチさせることができます。 a(b*c|c*d)
正規表現と有限ステートマシンには、同じような制限があります。
正規表現と有限状態機械にも同じような制限があります。特に、有限のメモリで処理できるパターンにしかマッチしない、または受け入れられないという点です。 例えば、’a’と’b’の文字列のみにマッチさせたいとします。 または、n個の’a’の後にn個の’b’が続く場合、nはある数です。
例としては、以下のようになります。
- ab
- aabb
- aaaaaabbbb
- aaaaaaaaaaaaabbbbbbbb
最初は、これは有限状態機械にとって簡単な仕事のように見えます。
たとえば、最大 20 個の「a」と 20 個の「b」を受け入れることができる有限ステート マシンを作成したとします。
認識できるすべての文字列に対して、機械がメモリ不足のために認識できない、ほんの少しだけ長い文字列があります。
これは Pumping Lemma として知られており、基本的には「パターンに (上記のように) 繰り返される部分がある場合、そのパターンは正規ではない」というものです。
言い換えると、正規表現も有限状態機械も、パターンに一致するすべての文字列を認識するようには構築できません。 どのタグのペアの中にも、他のマッチするタグのペアがいくつもあるかもしれません。
つまり、正規表現や有限状態機械を使って、ある HTML ページに <html>, <head><body> 要素を正しい順序で並べたとしても、正規表現を使って HTML ページ全体が有効かどうかを判断することはできません – HTML は正規パターンではないからです。
チューリング マシン
では、どのようにして非正規のパターンを認識するのでしょうか?
チューリング マシンと呼ばれる、ステート マシンに似た理論的な装置があります。 これは、紙の帯を持っていて、それを読み取るという点では、有限状態機械に似ています。
チューリング マシンについて説明するには、ここではスペースが足りませんが、有限状態マシンと正規表現の議論に関連するいくつかの重要なポイントがあります。
チューリング マシンは計算上完全です。つまり、計算できるものはすべてチューリング マシンで計算できます。
チューリング マシンは紙テープから読み取るだけでなく書き込むこともできるので、有限の数の状態に制限されません。 紙テープの長さは無限であると仮定できます。 もちろん、実際のコンピュータは無限のメモリを持っているわけではありません。
チューリングマシンは、計算プロセスがどのように機能するかを視覚化して理解することができる、想像上の機械装置を与えてくれます。 これは特に、計算の限界を理解するのに役立ちます。
Why does this matter?
では、何が重要なのでしょうか?
その限界はともかく、ステート マシンはコンピューティングの非常に中心的な概念です。 特に、あなたが設計できる非決定論的なステート マシンには、同じことを行う決定論的なステート マシンが存在することが重要です。
有限ステート マシンと正規表現が機能的に同等であることを理解することで、正規表現エンジンの非常に興味深い用途が開けます。特に、システムを再コンパイルせずに変更できるビジネス ルールを作成する場合などです。
コンピュータ サイエンスの基礎があれば、解き方のわからない問題を取り上げて、「Xの解き方はわからないが、Yの解き方はわかった。
原文はblog.markshead.comで2018年2月11日に公開されました。
また、新しいものを制作したときに時々メールを受け取りたい人のために、メーリングリストを用意しています。