第26話 作中に出てくる計算機科学用語集（２）
※この話は、特に本筋に関係ないので読み飛ばしてもらって構いません
この作品では、計算機科学
https://ja.wikipedia.org/wiki/%E8%A8%88%E7%AE%97%E6%A9%9F%E7%A7%91%E5%AD%A6
特に、理論計算機科学
https://ja.wikipedia.org/wiki/%E7%90%86%E8%AB%96%E8%A8%88%E7%AE%97%E6%A9%9F%E7%A7%91%E5%AD%A6
の分野の用語が説明なしにバシバシ出てきます。興味がある人向けにちょっとこれまで出てきた用語をリストアップしておきます。一応、わからなくても、雰囲気で楽しめるように書いている……つもりですが、知っておくとより面白い……かも？
・形式言語
自然言語と対比的に使われる用語で、文法や意味が曖昧でないという言語のことを指す。後述の形式文法とは深い関係にある。その応用範囲は幅広く、特にプログラマーなら知らず知らずのうちに恩恵を受けていることも。
https://ja.wikipedia.org/wiki/%E5%BD%A2%E5%BC%8F%E8%A8%80%E8%AA%9E
・形式文法
形式言語のための文法のこと。実際の歴史では、言語学者ノーム・チョムスキーがこの分野のパイオニア的存在。
https://ja.wikipedia.org/wiki/%E5%BD%A2%E5%BC%8F%E6%96%87%E6%B3%95
作中では、主人公とヒロインはこの分野を専門としている。
・文脈自由文法
形式文法の内の1つで、ノーム・チョムスキーが定式化したもの。現在の形式文法や形式言語の研究は、文脈自由文法をベースにしたものが取り扱われることが多い。
https://ja.wikipedia.org/wiki/%E6%96%87%E8%84%88%E8%87%AA%E7%94%B1%E6%96%87%E6%B3%95
・解析表現文法
2004年にBryan Fordが定式化した比較的新しい形式文法。特に、プログラミング言語の文法の定式化に向いているということで、ニッチではあるが細々と研究が続いているようである。
https://ja.wikipedia.org/wiki/Parsing_Expression_Grammar
・正規表現
プログラマーならお馴染みのアレ。正規表現の歴史は古いが、未だに研究が続けられているという意味で興味深い分野である。
・計算量
プログラムに対する入力を増やしていくと、どのように計算コストが増えるかを表す概念。代表的なものにランダウの記号がある。
https://ja.wikipedia.org/wiki/%E3%83%A9%E3%83%B3%E3%83%80%E3%82%A6%E3%81%AE%E8%A8%98%E5%8F%B7
・継続
プログラムにおいて、「残りの計算」を表す概念。継続の概念を言語機能として持った言語としてはSchemeなどが知られている。
https://ja.wikipedia.org/wiki/%E7%B6%99%E7%B6%9A
・NFA（Non-deterministic Finite Automata）
日本語では非決定性有限状態機械とも。正規表現と等価な能力を持つオートマトンのモデルの１つ。
・DFA（Deteminstic Finite Automata）
日本語では決定性有限状態機械とも。NFAに対してさらに強い制約をつけたオートマトンのモデルだが、NFAと同じ能力を持つことが知られている。
・構文解析器生成系
プログラミング言語などの分野において、「構文解析器」そのものを生成するためのツールの総称。作中でも出てきているが、GNU Bison（Yacc）、ANTLRなどが有名。1970年代頃に、「コンパイラを作るコンパイラ」の研究が流行った時期があって、その副産物として出来た……らしい。主人公らの専門分野ともそこそこ関わりがある。
・制約付きオートマトン（Constrained Automaton）
有限状態機械に対して、いくつかの制約条件を加えたオートマトン。NFA/DFAでは出来ない、「数のカウント」が出来る。詳細に立ち入るとめっちゃややこしくなるので割愛。
