syou6162 https://blog.hatena.ne.jp/syou6162/ yasuhisa's blog https://www.yasuhisay.info/ 計算理論 この前の続き。 DFAが受理する言語 NFAが受理する言語 正則表現が表す言語 は全て正則言語である、というのを示すのがメインテーマ。正則表現 => NFAの証明。正則表現に現われる演算子の数に関する帰納法で示す。分解していって、一個少ないから帰納法の仮定よりそれを満たすようなNFAを作れる(連接、閉包etcの3つの演算に関してこれをやる)。この証明がアルゴリズムっぽくなっているので、例はそれをやっていた(変形はやれるように練習しておかないと)。ただし、機械的に作るので冗長性が高くなっている(人間ならもっと簡単にできるんだが)。逆のNFA => 正則表現を考える(これができたら表現できる集合が… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fwww.yasuhisay.info%2Fentry%2F20100419%2F1271636130" title="正則言語と正則表現 - yasuhisa&#39;s blog" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2010-04-19 09:15:30 rich https://www.yasuhisay.info/entry/20100419/1271636130 1.0 100%