オートマトン

こんにちは、ももやまです。 オートマトンの理解度確認や復習をするための記事はまだ（ほとんど）ないと思います。 そこで4時間で復習が可能な、オートマトンと言語理論の総復習問題（うさぎ模試）を作成いたしました！ 使い方 90分間で問題を解く。問題3, 問題4についてはを回答フォームに入力する。 答えを送信後、間違った箇所を...

こんにちは、ももやまです。 今回は正規表現についてまとめてみました。 ただ正規表現についてまとめただけでなく、正規表現を有限オートマトンの状態遷移図で表す方法についてもまとめているのでそちらもご覧ください！ （正規表現について知りたい人は2章を、正規表現をオートマトンに直す方法が知りたい人は3章をご覧ください） 前回の...

こんにちは、ももやまです。 ほとんどの人がオートマトンという言葉を大学入学前に聞いたことはないと思います。大学などの授業で初めてオートマトンを習うとき、初めての概念で不安になってしまう人も多いと思います。 そこで今回は、オートマトンと言語理論ってどんなことを習うのかについてを簡単にですがダイジェスト方式でまとめていきた...

こんにちは、ももやまです。 今回はとある言語が正則かどうかを判定する練習、および正則だった場合に決定性オートマトンを書く練習、および正則でない場合に証明を書く練習をする総復習問題を作成しました。   ぜひ練習にお使いください。     前回の記事（第07羽）はこちら！ www.momoyama-usagi.com （文...

こんにちは、ももやまです。 今回はオートマトンと言語理論の中でも重要な文脈自由文法についてまとめていきたいと思います。 前回の記事の内容（Myhill-Nerodeの定理・正則ではない言語の証明法）はこちら↓ www.momoyama-usagi.com １．文脈自由文法とは 文脈自由文法は、以下の4つの要素で構成され...

記事修正履歴 9月23日：誤字・数式ミス修正、表現の微妙な修正をしました。指摘してくださった方、どうもありがとうございました！   こんにちは、ももやまです。 今までは決定性オートマトンを書いていくことを中心に説明していきました。 しかし今回は、いよいよみんなが(；´Д｀) うぅっ。。となる証明、具体的にはある言語が正...

こんにちは、ももやまです。 今回は決定性オートマトンを最小化する方法について説明していきたいと思います。 前回のオートマトン「第04羽」はこちら！↓ www.momoyama-usagi.com １．冗長な状態とは 例えば同じ操作*1を行う下のような2つの決定性オートマトンがあったとします。 このとき、下のオートマトン...

こんにちは、ももやまです。前回は言語の補集合、和、積、差を求め、決定性オートマトンで表す方法についてまとめましたね。 今回は言語の連接および閉包演算の結果を決定性オートマトンで表す方法についてまとめていきたいと思います。     前回の記事「言語の演算（前編）」はこちら！↓↓↓ www.momoyama-usagi.c...

こんにちは、ももやまです。今回はオートマトンの演算についてまとめていきましょう。     皆さん、和集合、積集合、差集合については覚えていますか？もし忘れてしまった人はこちらから復習しましょう！（少しだけですが使います） www.momoyama-usagi.com   前回のオートマトン「第02羽」はこちら↓ www...

こんにちは、ももやまです。 前回は決定性オートマトン(DFA)について説明しました。   今回は決定性ではないオートマトン、非決定性オートマトン(NFA)についてまとめていきたいと思います。   前回の決定性オートマトン（第01羽）についての記事はこちらから！ www.momoyama-usagi.com     １．...