講座系 オートマトン・言語と計算理論「チョムスキー標準形」
本シリーズでは、以下の本に沿って解説を書いている。前回は、正規言語は文脈自由言語であることを示した。今回以降の内容にどれだけ関わるかは微妙なところではあるが、重要な定理なのでこの事実だけでも押さえておきたい。以下がその記事だ。さて、今回はc...
2021-01
講座系 講座系 オートマトン・言語と計算理論「正規言語と文脈自由言語」
本シリーズでは、以下の本に沿って解説を書いている。前回は、cfgを考える時に便利な最左導出と導出木を解説した。まだ便利になる状況がそんなに出てきていないが、今後出てくる…はず。以下がその記事だ。さて、今回は以前扱っていた正規言語との関係につ...
講座系 オートマトン・言語と計算理論「最左導出と導出木」
本シリーズでは、以下の本に沿って解説を書いている。さて、前回から新しい単元である文脈自由文法に入った。これまでの内容との違いに気を付けながら進めていこう。以下がその記事だ。今回は、この文脈自由文法…cfgにおける、幾つか重要な性質について紹...
講座系 オートマトン・言語と計算理論「文脈自由文法」
本シリーズでは、以下の本に沿って解説を書いている。前回までで、正規文法編が完了だ。前回はその正規文法の名前の紹介と、正規文法には限界があるよという内容を解説した。以下がその記事だ。さて、今回から新しい内容、参考書で言うと第3章に入る。ここで...
講座系 オートマトン・言語と計算理論「正規言語とその限界」
本シリーズでは、以下の本に沿って解説を書いている。前回は、ある言語がnfaで認識できるなら、その言語を生成するような正規表現が存在することを示した。これで、これまで紹介した3種の有限オートマトンと正規表現がそれぞれ同じ言語を構成することが示...
講座系 オートマトン・言語と計算理論「正規表現とnfaの関係」
本シリーズでは、以下の本に沿って解説を書いている。前回は、ある言語が正規表現で生成可能なら、それを認識するような\(\varepsilon\)nfaが存在することを示した。こちら側はそこまで難しくなく、理解もしやすかったと思う。以下がその記...
紹介系 【ブレワイ】誰でもすぐできる！？RTAで使われている小技紹介
言わずと知れた名作「ゼルダの伝説 ブレスオブザワイルド」。ゼルダ初のオープンワールドで、すでに発売から3年以上経っている。もうやり込んでいる方も多いだろう。さて、最近RTA技で遊んでいる私だが、これまで紹介していたものはどれもかなり練習しな...
紹介系 【ブレワイ】スタイリッシュに敵を殲滅！【Thunderclap Rush解説】
言わずと知れた名作「ゼルダの伝説 ブレスオブザワイルド」。ゼルダ初のオープンワールドで、すでに発売から3年以上経っている。もうやり込んでいる方も多いだろう。さて、本シリーズではこれまで主にRTAで使われている技を解説してきた。しかし、今回の...
講座系 オートマトン・言語と計算理論「正規表現とεnfaの関係その1」
本シリーズでは、以下の本に沿って解説を書いている。前回は、nfaと\(\varepsilon\)nfaで認識できる言語に差がないことを示した。これで、dfa、nfa、\(\varepsilon\)nfaの3つそれぞれで認識できる言語に差がな...
紹介系 【ブレワイ】OPをスキップする壁抜け技【Scope Clip解説】
言わずと知れた名作「ゼルダの伝説 ブレスオブザワイルド」。ゼルダ初のオープンワールドで、すでに発売から3年以上経っている。もうやり込んでいる方も多いだろう。さて、本シリーズでは、RTAで使われている技を主に解説している。今回は、Scope ...