2026年度 (最新) 学院等開講科目工学院情報通信系

オートマトンと言語（情報通信）

開講元: 情報通信系
担当教員: 船越孝太郎 / 篠﨑隆宏
授業形態: 講義/演習 (対面型)
メディア利用科目: -
曜日・時限 (講義室): 不明
クラス: -
科目コード: ICT.H212
単位数: 210
開講時期: 2026年度
開講クォーター: 3Q
シラバス更新日: 2026年8月26日
使用言語: 日本語

シラバス

授業の目的（ねらい）、概要

プログラム言語処理と自然言語処理の基礎となる形式言語について，生成する手段と認識する機械の二つの観点から学ぶ．具体的な講義項目は，句構造文法，正規表現，正規文法，有限オートマトン，文脈自由文法，プッシュダウン・オートマトンなどである．

到達目標

プログラム言語処理と自然言語処理の基礎となる形式言語について，生成する手段（形式文法）と認識する機械（オートマトン）の二つの観点から学習する．

キーワード

句構造文法，正規表現，正規文法，有限オートマトン，文脈自由文法，プッシュダウン・オートマトン，形式言語

学生が身につける力

専門力
教養力
コミュニケーション力
展開力 (探究力又は設定力)
展開力 (実践力又は解決力)

授業の進め方

以下の授業計画にあるトピックの順で進める．ただし以下の計画の「回」は授業日（全14日）と直接対応しない．例えば月曜日は4時限で2回分を進めることがある．演習は基本的に講義と同じ時間枠の中で行い，講義日と演習日という分け方はしない．ただし演習のみの日も設けることがある．授業は日本語で行う．

授業計画・課題

	授業計画	課題
第1回	句構造文法	左記トピックについて理解する
第2回	正規文法	左記トピックについて理解する
第3回	有限オートマトン	左記トピックについて理解する
第4回	ε遷移を含むオートマトン	左記トピックについて理解する
第5回	決定性有限オートマトンの最小化	左記トピックについて理解する
第6回	正規言語の反復補題	左記トピックについて理解する
第7回	正規表現	左記トピックについて理解する
第8回	文脈自由文法 (CFG)	左記トピックについて理解する
第9回	チョムスキーの標準形	左記トピックについて理解する
第10回	文脈自由言語の反復補題	左記トピックについて理解する
第11回	非決定性プッシュダウンオートマトン (NPDA)	左記トピックについて理解する
第12回	NPDAとCFGの等価性	左記トピックについて理解する
第13回	文脈自由文法の性質	左記トピックについて理解する
第14回	決定性プッシュダウンオートマトン	左記トピックについて理解する

準備学修(事前学修・復習)等についての指示

学修効果を上げるため，教科書や配布資料等の該当箇所を参照し，「毎授業」授業内容に関する予習と復習（課題含む）をそれぞれ本学の学修規程で定められた時間を目安に行う。

教科書

コンピュータサイエンスのための言語理論入門，R. Smith 著，吉田敬一他訳，共立出版，1986

参考書、講義資料等

オートマトン，言語理論，計算論Ｉ[第2版](Introduction to Automata Theory, Languages, and Computation Second Edition) J. Hopcroft, R. Motowani, J. Ullman 著，野崎昭弘，高橋正子，町田元，山崎秀記訳，サイエンス社，2003

成績評価の方法及び基準

期末試験，演習により評価する．

履修の条件・注意事項

特になし