体系ガイド · 基礎から応用へ

形式言語・正規表現・有限オートマトン

文字列の集合を状態遷移で表し、有限の記憶で判定できる言語とできない言語を見分ける。

この記事をロゲイアに質問する確認問題3問に進むこれまでの誤答を復習する

更新日

この記事の目次
  1. 言語は文字列の集合
  2. 偶奇だけなら二つの状態で足りる
  3. DFAとNFAと正規表現
  4. 対応する括弧を無制限に覚えられるか
  5. この記事をロゲイアに質問する理解を確かめる

言語は文字列の集合

形式言語は、あるアルファベットから作る文字列の集合です。たとえば0と1からなる文字列のうち、1の個数が偶数のものを集められます。判定器は入力の見た目を説明するだけでなく、その文字列を集合に含めるかを決めます。空文字列も文字列の一つで、この例では1の個数が0なので受理します。文字列の長さや入力の終わりをどう扱うかを曖昧にすると、正規表現やプログラムの動作との比較で取り違えが起きます。

偶奇だけなら二つの状態で足りる

偶数個の1を読んだ状態Eと、奇数個の状態Oを用意します。0では状態を変えず、1ではEとOを入れ替えます。初期状態はE、受理状態もEです。入力101を読むとE→O→O→Eとなり受理します。途中で読んだ全ての文字を保存する必要はありません。将来の受理に関係する偶奇だけを記憶すれば十分だからです。有限オートマトンはこのように、入力の過去を有限個の同値な状況へまとめた機械として理解できます。

DFAとNFAと正規表現

DFAでは各状態と入力文字に対して次の状態が一つに決まります。NFAでは複数候補や空遷移を許し、いずれかの経路が受理すれば受理します。NFAからDFAへの変換では状態の集合を一つの状態として扱えますが、状態数が大きく増える場合があります。理論上の正規表現、DFA、NFAは同じ正規言語を表せます。ただし実用ライブラリの後方参照などは理論上の正規表現の演算とは異なります。機能が多い実装をそのまま有限状態の理論に当てはめないことが大切です。

対応する括弧を無制限に覚えられるか

aがn個続いた後にbがちょうどn個続く言語を考えます。nに上限がなければ、前半で読んだ個数の違いを有限個の状態だけで全て区別できません。鳩の巣原理や正規言語の性質を使うと、有限オートマトンではこの言語を認識できないことを示せます。入力長に小さな固定上限を設けた実装なら別で、その範囲を列挙する有限機械も作れます。言語の不可能性は無制限の入力に対する主張であり、現実の短いデータの検査が不可能だという意味ではありません。

読了と問題の結果を、言語ごとにこのブラウザへ保存します。

コースの順番に沿って学ぶ

CS基礎を固める · STEP 21

学習コースから次を選ぶ