講座系 オートマトン・言語と計算理論「チョムスキー標準形」
本シリーズでは、以下の本に沿って解説を書いている。 前回は、正規言語は文脈自由言語であることを示した。 今回以降の内容にどれだけ関わるかは微妙なところではあるが、重要な定理なのでこの事実だけでも押さえておきたい。 以下がその記事だ。 さて、...
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で使われている技を主に解説している。 今回は、Sc...