形式言語とオートマトンの講義ノートPDF。コンパイラや状態機械による言語処理の理論

講義ノートの目次へ

情報科学で，形式言語とオートマトンの講義ノートPDF。

コンパイラやチューリングマシンによる，機械的な言語処理を実現するための理論だ。

「正規言語」や「正規文法」といったモデル化を行なう。

ここで形式言語の処理を学ぶ前に，チューリングマシンが扱える問題の範囲を知っておくとよい。

計算量理論（チューリングマシンの計算複雑性・計算可能性）のノート

形式言語を学んだら，自然言語の処理へとステップアップしよう。

自然言語処理（形態素解析や文脈自由文法）のノート

形式言語とオートマトンの講義ノートPDF

しっかり学べるPDF：

数理情報科学シリーズ24　「オートマトンと形式言語の基礎」
http://p-www.iwate-pu.ac.jp/~k-yamada...

７６ページ。岩手県立大の「2013後期計算モデル論」の講義資料。

引用：

「有限オートマトンは…1940年代に神経回路網のモデルとして定義され、形式言語はチョムスキーによって、1950年代に自然言語やプログラミング言語のモデルとして導入された。…これらの研究成果は、コンパイラ、オペレーティングシステム、プログラミング言語、言語処理、論理回路、演算回路など、計算機科学のソフトウェアおよびハードウェアの設計に応用され、計算機工学の発展に多大な貢献をしてきた。」

「本書は、オートマトン・形式言語の入門書として、また、この分野を系統的に学ぶための教科書として書かれた。…筆者らは、入門書としての分かりやすさを維持しながら、上級のテーマについても、できるだけ平易で、直感的な記述を試みた。…各章の終わりに演習問題を用意し、巻末に演習問題の全問(60題)に解答をつけた。」

「本書の構成は次の通りである。第1章は導入部であり、集合、記号系列、言語、関数、関係、グラフ、アルゴリズム、証明技法など、このコースを学ぶために必要な予備的な基礎を述べている。第2章は、決定性有限オートマトン、非決定性有限オートマトン、正規表現、正規集合の性質を述べている。第3章は文脈自由言語、プッシュダウン・オートマトン、第4章は文脈自由言語の性質、構文解析を述べている。第5章は言語のハイアラーキーについて述べている。正規集合のクラス、文脈自由言語のクラスを真に包合する言語のクラスとして、文脈依存言語のクラス、句構造言語のクラスが第5章のテーマである。各言語クラスについて、いろいろな演算の閉包性、いろいろな決定問題が可解であるか否かの比較をこの章の終わりに与えている。」

　第1章　基礎的な準備
　第2章　有限オートマトン
　第3章　文脈自由言語
　第4章　文脈自由言語の性質
　第5章　言語のハイアラーキー
続き：http://p-www.iwate-pu.ac.jp/~k-yamada/lecture/model2013/text_b2013.pdf
　1　機械モデル（チューリングマシンと計算複雑性・計算可能性）
　2　１階述語論理と論理プログラミング

形式言語とオートマトン講義資料
http://www.eonet.ne.jp/~tktkhaya/flaa...

立命館大の講義資料。

引用：「当講義は記号と記号列に関する数学すなわち形式言語理論(formal language theory)への導入を目的としている。」

　第 1 講あらましと予備知識
　第 2 講記号列
　第 3 講言語の定義と操作
　第 4 講言語の種類
　第 5 講正規言語と正規表現
　第 6 講抽象機械
　第 7 講決定的有限状態機械
　第 8 講有限状態機械の設計
　第 9 講非決定的有限状態機械
　第 10 講 DFA と NFA
　第 11 講 FSA が定義する言語
　第 12 講 FSA と正規言語
　第 13 講正規言語のポンピング定理
　第 14 講スタック機械とテープ機械
　第 15 講 DPDA と NPDA
　第 16 講 DTM と NTM
　第 17 講文法
　第 18 講正規文法と正規言語
　第 19 講文脈自由言語

「形式言語とオートマトン」
http://www.fu.is.saga-u.ac.jp/~yaman/...

佐賀大の講義資料。１１６ページ。重要語句が穴埋め形式で書き込み済み。

　第1章はじめに
　第2章復習
　第3章記号列と言語
　第4章正則表現
　第5章決定性有限状態オートマトン
　第6章非決定性有限状態オートマトン
　第7章 ε-遷移を含む非決定性有限状態オートマトン
　第8章正則表現（ふたたび）
　第9章決定性有限状態オートマトンの最小化
　第10章字句解析器生成系lex
　第11章出力付きオートマトン
　第12章文脈自由文法
　第13章プッシュダウン・オートマトン
　第14章チョムスキー階層
　第15章チューリング・マシーン

電子情報通信学会知識ベース｜2編　計算論とオートマトン
http://www.ieice-hbkb.org/portal/doc_...

−電子情報通信学会の知識ベース。

　1章オートマトンと言語
　2章有限オートマトンと正則表現
　3章文脈自由文法とプッシュダウンオートマトン
　4章チューリング機械

スライドPDF：

オートマトンと言語（2012）
http://www.ccn.yamanashi.ac.jp/~ysuzu...

山梨大の講義スライド。

　1　オートマトンとは，オリエンテーション
　2　数式の記法，スタック，BNF
　3　BNF，グラフ
　4　グラフ
　5　有限オートマトン
　6　有限オートマトン
　7　正規表現
　8　正規表現，非決定性有限オートマトン
　10　NFA→DFA
　11　DFAの最小化
　12　DFAの最小化，有限オートマトンの応用
　13　プッシュダウンオートマトン，チューリング機械
　14　文脈自由文法

オートマトンと形式言語（2007）
http://kurt.scitec.kobe-u.ac.jp/~kiky...

神戸大の講義スライド。

　NFAとDFA
　NFAとDFAの等価性
　ε-NFA
　正規表現
　NFAの正規表現への変換
　NFAの反復補題
　生成文法
　正規文法と正規言語
　DFAの最小化
　正規言語のその他の性質
　文脈自由言語の例や性質
　CFGとPDA

平成18年度オートマトンと形式言語 (Automata and Formal Languages) @能美キャンパス
http://www.jaist.ac.jp/~uehara/course...

北陸先端技術大の講義スライド。

　(1)数学的準備
　(2)有限オートマトン(1)
　(3)有限オートマトン(2)
　(4)正則表現
　(5)正則集合(1)
　(6)正則集合(2)
　(7)文脈自由文法(1)
　(8)文脈自由文法(2)
　(9)文脈自由文法(3)
　(10)プッシュダウンオートマトン(1)
　(11)プッシュダウンオートマトン(2)
　(12)チューリング機械(1)
　(13)チューリング機械(2)
　(14)決定不能性

計算理論
http://ocw.kyushu-u.ac.jp/0005/0003/l...

九州大の講義スライド。

　2.有限オートマトン
　3.文脈自由言語
　5.文脈依存言語

プログラマ向け：

競技プログラマ向け　形式言語理論入門
http://www.kmonos.net/pub/Presen/JOI_...

９８ページのスライド。

Webページ形式で読めるノート：

言語処理（2012）
http://home.a00.itscom.net/hatada/_to...

制作演習つき。

　１．プログラミング言語の基本概念
　２．形式言語の構文と意味
　３．形式言語と処理機械（オートマトン）の関係
　　３A．C言語による字句解析
　４．コンパイラとインタプリタおよびそのITへの応用
　５B．制作演習の進め方
　５C．字句解析
　６．C言語の言語仕様
　　６A．構文解析法
　　６B．ci.cでの構文解析
　　６C．cc0.cでの構文解析
　７．意味解析・コード生成
　　７A．パーサー

問題と解答：

オートマトン・形式言語及び演習
http://www.trs.cm.is.nagoya-u.ac.jp/~...

名古屋大の演習。