Web Analytics Made Easy - StatCounter

工業大学生ももやまのうさぎ塾

うさぎでもわかるをモットーに大学レベルの数学・情報科目をわかりやすく解説!

情報-オートマトン

うさぎでもわかるオートマトンと言語理論 第09羽 正規表現と有限オートマトン

今回は正規表現について簡単にですがまとめています。よく使われる正規表現の種類、正規表現を非決定性オートマトンで表す方法を例題や練習問題を踏まえながらわかりやすくまとめています。

うさぎでもわかるオートマトンと言語理論 第00羽 オートマトンのいろは

今回はまだオートマトンを習ったことのない人向けにオートマトンと言語理論ってどんなことを学ぶんだろうというのをダイジェスト形式でわかりやすくまとめてみました。

うさぎでもわかるオートマトンと言語理論 第08羽 総復習・正則言語の判定

今回はオートマトンと言語理論の総復習として、とある言語が正則であるかどうかの判定、正則だった場合に決定性オートマトンを書く練習、および正則でなかった場合にMyhill-Nerodeの定理をうまく利用して証明をする練習問題を作成しました。

うさぎでもわかるオートマトンと言語理論 第07羽 文脈自由文法

今回は、オートマトンと言語理論の中でも重要な文脈自由文法についてまとめました。文脈自由文法を読む方法、正規文法、チョムスキー(Chomsky)標準形、グライバッハ(Greibach)標準形とはどのような文脈自由文法なのかについてまとめています。

うさぎでもわかるオートマトンと言語理論 第06羽 Myhill-Nerodeの定理・正則でない言語の証明法

今回はオートマトンと言語理論においても重要なMyhill-Nerodeの定理についてまとめていきました。有限指数、右不変の意味、Myhill-Nerodeの定理、正則ではない言語、つまり有限オートマトンが記述できない言語であることを示すための応用法についてまとめて…

うさぎでもわかるオートマトンと言語理論 第05羽 決定性オートマトンの最小化

今回は冗長な状態がある決定性オートマトンの冗長部分をなくし、より単純な決定性オートマトンに変形する方法についてまとめています。

うさぎでもわかるオートマトンと言語理論 第04羽 言語の演算(後編) 連接・閉包

今回は、オートマトンにおける2つの言語を連接させて新たな言語を作成する言語の連接演算や、言語の繰り返しを表すカーネル閉包(スター閉包)の演算方法などについてまとめています。

うさぎでもわかるオートマトンと言語理論 第03羽 オートマトンの演算(前編)

今回はオートマトンの演算における、補集合演算、和についての演算、積についての演算、差についての演算について例や練習問題を含めながらまとめています。

うさぎでもわかるオートマトンと言語理論 第02羽 非決定性オートマトン(NFA)の書き方・決定性オートマトン(DFA)への変換

今回はオートマトンの中でも、より直感的に書くことができる非決定性オートマトン(NFA)の特徴、非決定性オートマトンの書き方、非決定性オートマトン(NFA)を決定性オートマトン(DFA)に直す方法についてまとめています。

うさぎでもわかるオートマトンと言語理論 第01羽 決定性オートマトン(DFA)とは

この記事ではオートマトンの中でも決定性オートマトンとはどんなものかについてをすごろくに例えて説明しています。また、決定性オートマトンの読み方、および決定性オートマトンの書き方についてを説明しています。