講座系

解説メイン。中には勉強した結果も。

講座系

オートマトン・言語と計算理論「正規言語とその限界」

本シリーズでは、以下の本に沿って解説を書いている。 前回は、ある言語がnfaで認識できるなら、その言語を生成するような正規表現が存在することを示した。 これで、これまで紹介した3種の有限オートマトンと正規表現がそれぞれ...
講座系

オートマトン・言語と計算理論「正規表現とnfaの関係」

本シリーズでは、以下の本に沿って解説を書いている。 前回は、ある言語が正規表現で生成可能なら、それを認識するような\(\varepsilon\)nfaが存在することを示した。 こちら側はそこまで難しくなく、理解もしやす...
講座系

オートマトン・言語と計算理論「正規表現とεnfaの関係その1」

本シリーズでは、以下の本に沿って解説を書いている。 前回は、nfaと\(\varepsilon\)nfaで認識できる言語に差がないことを示した。 これで、dfa、nfa、\(\varepsilon\)nfaの3つそれぞ...
講座系

オートマトン・言語と計算理論「nfaとεnfaの関係」

本シリーズでは、以下の本に沿って解説を書いている。 前回は、またしても新しい有限オートマトンである\(\varepsilon\)入力付き非決定性有限オートマトンを解説した。 状態遷移でこれまでに使っていなかった様相やス...
講座系

オートマトン・言語と計算理論「ε入力付き非決定性有限オートマトン」

本シリーズでは、以下の本に沿って解説を書いている。 前回は、決定性有限オートマトンと非決定性有限オートマトンそれぞれで、認識できる言語に差がないことを証明した。 また、その中で非決定性有限オートマトンを決定性に書き換え...
講座系

【数学】集合の要素同士を対応させる「写像」

今、シリーズでオートマトンと言語に関する話を書いている。 初回は以下だ。 前回は証明をざっとではあるが解説した。 これは数をこなせばこなすほど、RPGのレベルのように実力が上がっていくので、是非色々調べてチャ...
講座系

【数学】証明って何だろう

今、シリーズでオートマトンと言語に関する話を書いている。 初回は以下だ。 さて、前回は証明の解説の準備として、命題と論理を解説した。 改めて言葉で見るとなかなかに難しそうだが、適宜真偽関係を見ながら進めてもら...
講座系

【数学】証明のための「命題と論理」

今、シリーズでオートマトンと言語に関する話を書いている。 初回は以下だ。 さて、前回から必要な知識の補足を書いている。 前回は、集合とは何ぞやというところを解説した。 本当に基礎の部分しか解説していない...
講座系

【数学】「集合」の定義と基本的な性質

今、シリーズでオートマトンと言語に関する話を書いている。 初回は以下だ。 さて、ここで集合だったり論理だったりをガンガン使っている。 しかし、そのあたりが不安な方もいらっしゃるのではないだろうか。 特に...
講座系

オートマトン・言語と計算理論「決定性と非決定性の関係」

本シリーズでは、以下の本に沿って解説を書いている。 前回は新しい単元に進んで、非決定性有限オートマトンというものを定義した。 前々回までの決定性有限オートマトンとは異なり、同じ記号による遷移先が複数になったり、空集合に...
スポンサーリンク
タイトルとURLをコピーしました