読者です 読者をやめる 読者になる 読者になる
スポンサーリンク

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

正規表現 計算機科学 講義ノート リンク集 アルゴリズム テキスト処理


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


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

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


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

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

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

しっかり学べるPDF:

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

  • 76ページ。岩手県立大の「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 1階述語論理と論理プログラミング


形式言語とオートマトン講義資料
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/...

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

 第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_...

  • 98ページのスライド。


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

言語処理(2012)
http://home.a00.itscom.net/hatada/_to...

  • 制作演習つき。

 1.プログラミング言語の基本概念
 2.形式言語の構文と意味
 3.形式言語と処理機械(オートマトン)の関係
  3A.C言語による字句解析
 4.コンパイラとインタプリタおよびそのITへの応用
 5B.制作演習の進め方
 5C.字句解析
 6.C言語の言語仕様
  6A.構文解析法
  6B.ci.cでの構文解析
  6C.cc0.cでの構文解析
 7.意味解析・コード生成
  7A.パーサー


問題と解答:

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

  • 名古屋大の演習。

関連する記事:

あなたが正規表現の中級者か判別する10問テスト (文字列処理の必須知識)
http://language-and-engineering.hatenablog.jp/entry/20131028/RegExpProgrammin...


「グラフ理論」と「組み合わせ最適化アルゴリズム」の教科書PDF。離散数学の入門用の教科書
http://language-and-engineering.hatenablog.jp/entry/20140528/GraphTheoryPDFLe...


ゲーム理論の講義ノートPDF。応用を含めた講義資料 (戦略と意思決定の方法論)
http://language-and-engineering.hatenablog.jp/entry/20140516/GameTheoryPDFNot...


「ラムダ計算」を独学で学習するための,講義ノートやPDFのリンク集 (復習用の問題付き)
http://language-and-engineering.hatenablog.jp/entry/20130313/LambdaCalculusBa...