講座系 オートマトン・言語と計算理論「文脈自由文法」
本シリーズでは、以下の本に沿って解説を書いている。前回までで、正規文法編が完了だ。前回はその正規文法の名前の紹介と、正規文法には限界があるよという内容を解説した。以下がその記事だ。さて、今回から新しい内容、参考書で言うと第3章に入る。ここで...
講座系
講座系 講座系 オートマトン・言語と計算理論「正規言語とその限界」
本シリーズでは、以下の本に沿って解説を書いている。前回は、ある言語がnfaで認識できるなら、その言語を生成するような正規表現が存在することを示した。これで、これまで紹介した3種の有限オートマトンと正規表現がそれぞれ同じ言語を構成することが示...
講座系 オートマトン・言語と計算理論「正規表現とnfaの関係」
本シリーズでは、以下の本に沿って解説を書いている。前回は、ある言語が正規表現で生成可能なら、それを認識するような\(\varepsilon\)nfaが存在することを示した。こちら側はそこまで難しくなく、理解もしやすかったと思う。以下がその記...
講座系 オートマトン・言語と計算理論「正規表現とεnfaの関係その1」
本シリーズでは、以下の本に沿って解説を書いている。前回は、nfaと\(\varepsilon\)nfaで認識できる言語に差がないことを示した。これで、dfa、nfa、\(\varepsilon\)nfaの3つそれぞれで認識できる言語に差がな...
講座系 オートマトン・言語と計算理論「nfaとεnfaの関係」
本シリーズでは、以下の本に沿って解説を書いている。前回は、またしても新しい有限オートマトンである\(\varepsilon\)入力付き非決定性有限オートマトンを解説した。状態遷移でこれまでに使っていなかった様相やステップといった概念を導入し...
講座系 オートマトン・言語と計算理論「ε入力付き非決定性有限オートマトン」
本シリーズでは、以下の本に沿って解説を書いている。前回は、決定性有限オートマトンと非決定性有限オートマトンそれぞれで、認識できる言語に差がないことを証明した。また、その中で非決定性有限オートマトンを決定性に書き換える方法も解説した。それぞれ...
講座系 【数学】集合の要素同士を対応させる「写像」
今、シリーズでオートマトンと言語に関する話を書いている。初回は以下だ。前回は証明をざっとではあるが解説した。これは数をこなせばこなすほど、RPGのレベルのように実力が上がっていくので、是非色々調べてチャレンジして頂きたい。以下がその記事だ。...
講座系 【数学】証明って何だろう
今、シリーズでオートマトンと言語に関する話を書いている。初回は以下だ。さて、前回は証明の解説の準備として、命題と論理を解説した。改めて言葉で見るとなかなかに難しそうだが、適宜真偽関係を見ながら進めてもらえればと思う。前回の記事は以下だ。…と...
講座系 【数学】証明のための「命題と論理」
今、シリーズでオートマトンと言語に関する話を書いている。初回は以下だ。さて、前回から必要な知識の補足を書いている。前回は、集合とは何ぞやというところを解説した。本当に基礎の部分しか解説していないが、一旦集合が何者かは理解できたと思う。以下が...
講座系 【数学】「集合」の定義と基本的な性質
今、シリーズでオートマトンと言語に関する話を書いている。初回は以下だ。さて、ここで集合だったり論理だったりをガンガン使っている。しかし、そのあたりが不安な方もいらっしゃるのではないだろうか。特に、文系の方だとこのあたりはそもそも習ったかどう...