オートマトン｜シラバス情報

科目授業名称（和文）　Name of the subject/class (in Japanese)

オートマトン

科目授業名称（英文）　Name of the subject/class (in English)

Automata30

授業コード　Class code

9963514

科目番号　Course number

63CSALC301

教員名

東条　敏

Instructor

Satoshi Tojo

開講年度学期

2026年度後期

Year

2026年度

Semester

②Second semester

曜日時限

火曜4限

Class hours

Tuesday 14:40--16:10

開講学科・専攻　Department

創域理工学部　情報計算科学科、数理科学科

Department of Information Sciences, Faculty of Science and Technology
Department of Mathematics Faculty of Science and Technology

単位数　Course credit

2.00単位

授業の方法　Teaching method

講義

Lecture

外国語のみの科目（使用言語）　Course in only foreign languages (languages)

-

授業の主な実施形態　Main class format

① [対面]対面授業/ [On-site] On-site class

概要　Description

オートマトン理論と形式言語理論は計算機機科学を構成する理論の中で最も基礎的な理論である。この理論は多くの他の分野で必要とされる。例えば、ハードウェアでは論理回路、ソフトウェアではコンパイラの構成等。ここでは、それらの基礎を学び概念を習得する。

目的　Objectives

有限オートマトン、プッシュダウンオートマトン、チューリング機械、正規表現、文脈自由文法の基礎概念を理解し、それらの言語との関係を学ぶ。これによって、各種コンピュータ分野が緊密な関係をもつということを理解する能力を得る。
　本学科のディプロマポリシー「情報科学分野に応じた基礎学力と、その上に立つ専門知識を身に付けている」に該当する科目である。

到達目標　Outcomes

１．形式言語・オートマトン理論における記号列と言語について述べる。言語の認識機構としてのオートマトンと言語の生成機構としての形式文法を理解する。
２．有限オートマトン、プッシュダウンオートマトンおよびチューリング機械の概念、それらの言語との関係を理解する。
３．正規表現の概念および有限オートマトンとの関係を理解する。
４．チョムスキーの形式文法、特に文脈自由文法を学び、オートマトンとの関係を理解する。

卒業認定・学位授与の方針との関係（学部科目のみ）

リンク先の [評価項目と科目の対応一覧]から確認できます（学部対象）。
履修登録の際に参照ください。
You can check this from “Correspondence table between grading items and subjects” by following the link(for departments).
https://www.tus.ac.jp/fd/ict_tusrubric/

履修上の注意　Course notes prerequisites

原則、対面形式で講義を行う。講義資料をLETUS上で配布する。

アクティブ・ラーニング科目　Teaching type（Active Learning）

-

準備学習・復習　Preparation and review

配布講義資料で準備学習と授業相当の学習を各２時間ほど行い，講義資料中の演習で，授業後の復習を行う。

成績評価方法　Performance grading policy

小テストを三回授業内に行い，それぞれ40％，40％，20％ずつを加算して評価する．

学修成果の評価　Evaluation of academic achievement

・S：到達目標を十分に達成し、極めて優秀な成果を収めている
・A：到達目標を十分に達成している
・B：到達目標を達成している
・C：到達目標を最低限達成している
・D：到達目標を達成していない
・-：学修成果の評価を判断する要件を欠格している

・S：Achieved outcomes, excellent result
・A：Achieved outcomes, good result
・B：Achieved outcomes
・C：Minimally achieved outcomes
・D：Did not achieve outcomes
・-：Failed to meet even the minimal requirements for evaluation

教科書　Textbooks/Readings

教科書の使用有無（有=Y , 無=N）　Textbook used(Y for yes, N for no)

N

書誌情報　Bibliographic information

-

MyKiTSのURL（教科書販売サイト）　URL for MyKiTS(textbook sales site)

教科書および一部の参考書は、MyKiTS (教科書販売サイト) から検索・購入可能です。
https://gomykits.kinokuniya.co.jp/tokyorika/

It is possible to search for and purchase textbooks and certain reference materials at MyKiTS (online textbook store).
https://gomykits.kinokuniya.co.jp/tokyorika/

参考書・その他資料　Reference and other materials

Dexter C. Kozen, Automata and Computability, Springer, 1997
J. E. Hopcroft, R. Motowani, and J.D. Ullman.: Introduction to Automata Theory, Language, and Computation, Addison-Wesley
(和訳：野崎昭弘他訳，ホップクロフト，モトワニ，ウルマン『言語理論計算論 I』サイエンス社第3版)
M. Sipser: Introduction to the Theory of Computation, Cengage Learning
(和訳：田中圭介監訳，M.シプサ．計算理論の基礎(1))

授業計画　Class plan

受業は対面で実施する．

1. 有限文字列と文字列への操作を理解し，決定性有限オートマトンとその受理言語について講義する．

2. 非決定性オートマトンを定義し，決定性オートマトンとの等価性を証明する．

3. イプシロン遷移を含むオートマトンを導入する．また，正規表現を導入する．

4. 正規言語と有限オートマトンの等価性について講義する．

5. 正規言語の閉包性，および準同型について講義する．

6. 有限オートマトンのポンプの補題を証明し，最小化の手続きについて講義する．

7. Myhill-Nerodeの定理について講義し，授業内小テスト(1)を行う．

8. 文脈自由文法を定義し，イプシロン生成・単項生成の除去を行う．

9. チョムスキー標準形を定義し，CKYパーサについて講義する．

10. 文脈自由言語のポンプの補題を証明する．またプッシュダウンオートマトンを導入する．

11. プッシュダウンオートマトンの諸性質について概説する．

12. プッシュダウンオートマトンの一状態化を行い，グライバッハの標準形を定義する．

13. プッシュダウンオートマトンと文脈自由文法の等価性，授業内小テスト(2)を行う．

14. チョムスキー階層およびその中での正規文法を講義する．

15. 線形有界オートマトンを講義し，授業内小テスト(3)を行う．

担当教員の実務経験とそれを活かした教育内容　Work experience of the instructor

-

教育用ソフトウェア　Educational software

-

備考　Remarks

授業でのBYOD PCの利用有無　Whether or not students may use BYOD PCs in class

Y

授業での仮想PCの利用有無　Whether or not students may use a virtual PC in class

N