コンパイラ：第3回

• 実施日：2008-04-30（水）1限
• 講義内容：正則表現と有限オートマトン
• 講義ノート：2章（既配布分の続き）

この講義では、正則表現（正規表現、regular expression）と有限オートマトン（finite automaton）という概念を説明しました。これらは情報科学では非常に重要なもので、コンパイラに限らず、文字列検索、通信プロトコルなど、あちこちで登場します。是非、この機会に知っておいてください。

なお、今日お話しした有限オートマトンは決定性有限オートマトン（deterministic finite automaton, DFA）というものですが、理解しやすくするため、一部（未定義の遷移の扱い）で定義を簡単にしています。厳密な議論は大学院の講義「形式言語理論」で扱います。