シラバス参照

講義概要/Course Information
2020/04/28 現在

科目基礎情報/General Information
授業科目名
/Course title (Japanese)
形式言語理論
英文授業科目名
/Course title (English)
Formal Language Theory
科目番号
/Code
INS402a INS402c INS402d
開講年度
/Academic year
2020年度 開講年次
/Year offered
2
開講学期
/Semester(s) offered
後学期 開講コース・課程
/Faculty offering the course
情報理工学域
授業の方法
/Teaching method
講義 単位数
/Credits
2
科目区分
/Category
専門科目
開講学科・専攻
/Cluster/Department
Ⅰ類
担当教員名
/Lecturer(s)
伊藤 大雄
居室
/Office
西9-505
公開E-Mail
/e-mail
itohiro@uec.ac.jp
授業関連Webページ
/Course website
特に無し
更新日
/Last updated
2020/02/20 18:15:16 更新状況
/Update status
公開中
/now open to public
講義情報/Course Description
主題および
達成目標
/Topic and goals
以下の事項を理解することを目標とする。
・有限オートマトンと状態遷移図の概念
・非決定性有限オートマトンを通じて非決定性の概念
・正則でない言語とその証明法
前もって履修
しておくべき科目
/Prerequisites
離散数学
前もって履修しておくこ
とが望ましい科目
/Recommended prerequisites and preparation
特になし
教科書等
/Course textbooks and materials
岩田、笠井著:有限オートマトン入門、森北出版
授業内容と
その進め方
/Course outline and weekly schedule
有限オートマトンと形式言語に関する事項を講義する。
第1回:機械と言語
第2回:関係と反射推移閉包
第3回:同値関係
第4回:状態遷移図と有限オートマトン(DFA)
第5回:有限オートマトンの形式的定義
第6回:非決定性有限オートマトン(NFA)
第7回:非決定性有限オートマトンで受理する言語
第8回:NFAと同値なDFAの具体的構成法
第9回:空動作を有する非決定性有限オートマトン
第10回:正則表現
第11回:正則表現と有限オートマトン
第12回:右不変同値関係と正則集合
第13回:正則でない言語
第14回:文法と正則文法
第15回:チョムスキー階層
実務経験を活かした
授業内容
(実務経験内容も含む)
/Course content utilizing practical experience
授業時間外の学習
(予習・復習等)
/Preparation and review outside class
教科書の演習問題を解いておくこと。
成績評価方法
および評価基準
(最低達成基準を含む)
/Evaluation and grading
原則として期末試験の結果で評価する。講義中の積極的な参加、発言も考慮する。講義で解説した項目を理解することを最低達成基準とする。
オフィスアワー:
授業相談
/Office hours
原則として講義の後に質問に来る事。その他はメールで面談時間を予約すること。
学生へのメッセージ
/Message for students
形式言語理論の基本概念は、情報工学のみならず、工学全体で必要な基本的概念の一つである。
その他
/Others
特になし
キーワード
/Keyword(s)
有限オートマトン、状態遷移図、非決定性、正則表現、正則言語、文法