計算理論
期末 教科書ノート

チューリング機械（ちゅーりんぐきかい）とは、

無限テープと読み書きヘッドと有限状態で、計算の手順を機械的に実行するモデル。

別名: TM / Turing machine。本稿では TM と併記。

なぜ出るか: 期末の選択・記述・作文の共通土台。『コンピュータで解ける』の上限を測る物差し。

[前] 人間が暗算で手順を進める
  -->
[後] 同じ手順を δ の規則だけで自動実行

仕組み（言葉）: 今の状態とヘッド下の記号を見て、書く・動く・状態を変える。これを繰り返す。

試験での答え方: 「テープ＋ヘッド＋状態の計算モデル。FA/PDAより認識能力が高い」と一文。

状態遷移関数 δ（でるた）とは、

「今の状態と読んだ記号」から「次状態・書く記号・ヘッドの動き」を決める規則表。

別名: 遷移関数 / transition function。

なぜ出るか: 期末問2の空欄はすべて δ の穴埋め。暗記より『保持している情報は状態に載る』が鍵。

[前] δ(q, a) = (p, b, R)
  -->
[後] 状態qでaを見たら bを書き pになり 右へ1マス

仕組み（言葉）: 1行が1命令。ジャンプや同時2マス読みはできない。

試験での答え方: δ(q,a)=(p,b,D) を『読む・書く・動く・状態更新』の4語で説明する。

有限オートマトン（ゆうげんおーとまとん）とは、

有限個の状態だけで入力を左から読む機械。正規言語を認識する。

別名: FA / DFA / NFA（本稿では FA）。

なぜ出るか: 階層比較と『FAがあれば正規文法・TMもある』型の選択問題の土台。

[前] メモリ無しの自動ドア
  -->
[後] 今の状態と次の記号だけで次状態が決まる

仕組み（言葉）: スタックもテープ書き換えもない。だから能力はTMより弱い。

試験での答え方: 「有限状態のみ。正規言語を認識」と書く。

プッシュダウンオートマトン（ぷっしゅだうんおーとまとん）とは、

有限状態にスタック（後入れ先出し）を足した機械。文脈自由言語を認識する。

別名: PDA。

なぜ出るか: FA＜PDA＜TM の階段と、基本情報のスタック操作問題の橋渡し。

[前] FA（メモ無し）
  -->
[後] PDA（積み上げた記号を上から使う）

仕組み（言葉）: PUSHで積み、POPで取り出す。途中の要素には触れない。

試験での答え方: 「スタック付きオートマトン。文脈自由言語」と対応づけて書く。

言語の能力の階段（のうりょくのかいだん）とは、

FA⊂PDA⊂TM（認識能力）。正規⊂文脈自由⊂…⊂句構造、と同じ向きの包含。

別名: 計算モデルの階層 / チョムスキー階層と対応。

なぜ出るか: 期末問1(1)(2)の直撃。『下位ができれば上位の機械も存在する』。

[前] 正規言語（FA）
  --> 文脈自由（PDA）
  --> 句構造 / TM認識可能

仕組み（言葉）: 弱い機械で認識できる言語は、強い機械でも認識できる（変換・シミュレーション）。

試験での答え方: 包含の向きを矢印で書き、FA⇒正規文法・TMの存在を主張する。

チョムスキー階層（ちょむすきーかいそう）とは、

文法の種類で言語を層分けした図。正規⊂文脈自由⊂文脈依存⊂句構造。

別名: Chomsky hierarchy。

なぜ出るか: 期末問1(2)。『文脈自由は正規を包含』『句構造にしか入らない言語がある』。

[前] 小さな円: 正規
  -->
[後] それを囲む大きな円: 文脈自由 → さらに句構造

仕組み（言葉）: 生成規則の形を厳しくすると扱える言語が減る。

試験での答え方: 包含関係を包含記号で書き、反例言語の存在に触れる。

形式文法（けいしきぶんぽう）とは、

G=(N,T,P,S)。非終端・終端・生成規則・開始記号の4つ組で言語を生成する装置。

別名: 文法 / formal grammar。開始記号は S や A。

なぜ出るか: 期末問1(4)。記号の役割（εは非終端ではない等）を正確に言えるか。

[前] 開始記号 A
  --> 規則で書き換え
[後] 終端だけが残った文字列 = 生成された語

仕組み（言葉）: 左辺を右辺に置き換える。終端だけになったら完成。

試験での答え方: 四つ組を書き、各集合の所属を1つずつ判定する。

正規文法（せいきぶんぽう）とは、

生成規則が右線形（または左線形）だけに制限された文法。正規言語を生成する。

別名: regular grammar。FAと対。

なぜ出るか: 『FAがある⇔正規文法がある』系の選択。文脈自由との区別。

[前] A → aB または A → a （右線形）
  -->
[後] 状態遷移とほぼ同じ形

仕組み（言葉）: 非終端は高々1つ、しかも端にしか置かない。

試験での答え方: 規則の形を見て正規かどうかを判定、と書く。

文脈自由文法 CFG（ぶんみゃくじゆうぶんぽう）とは、

左辺が単一の非終端だけの文法。文脈自由言語を生成する。

別名: context-free grammar / CFG。

なぜ出るか: 階層問題と、期末文法記号問題の『これは正規か文脈自由か』。

[前] A → aAb | ε
  -->
[後] どんな前後があっても A を書き換えられる（文脈自由）

仕組み（言葉）: 左右の文脈を見ない。だから『文脈自由』。

試験での答え方: 「左辺が非終端1つ」と定義を書く。

判定可能（はんていかのう）とは、

どんな入力でも必ず停止して yes/no を返すアルゴリズム（判定装置）が存在する性質。

別名: decidable / recursive。

なぜ出るか: 第10–12回の本線。ATM・HALTTM・ETM は判定不可能。

[前] 聞きたい yes/no 問題
  -->
[後] いつも止まって答える機械がある = 判定可能

仕組み（言葉）: 認識可能より強い。拒否する場合もループせず停止する。

試験での答え方: 「常に停止する判定装置が存在する」と定義を書く。

Turing認識可能（ちゅーりんぐにんしきかのう）とは、

受理すべき入力では必ず停止受理するTMがあること。拒否側はループしてよい。

別名: RE / Turing-recognizable / 半判定可能。

なぜ出るか: ATMは認識可能だが判定不可能。補認識可能とのセットが第11回。

[前] 受理なら止まる
  -->
[後] 非受理は拒否停止でもループでもよい

仕組み（言葉）: 『見つかったら受理』型。見つからない証明は難しい。

試験での答え方: 判定可能との差（非受理時の停止義務）を対比して書く。

決定不能問題（けっていふのうもんだい）とは、

それを解く（常に停止する）手順が存在しない問題。

別名: 判定不可能問題 / undecidable problem。

なぜ出るか: 期末問1(3)の定義そのもの。『答えられない』ではなく『手順が無い』。

[前] 解き方を探す
  -->
[後] どんな手順を書いても必ず失敗する入力がある

仕組み（言葉）: 証明は帰着や対角線。感覚的な難しさではない。

試験での答え方: 「問題を解く手順が存在しない」を選ぶ／書く。

受理問題 ATM（じゅりもんだい）とは、

ATM={〈M,w〉| MはTMで w を受理する}。判定不可能の代表例。

別名: acceptance problem / A_TM。

なぜ出るか: 第10回。他の判定不可能性はだいたいここから帰着する。

[前] 〈M,w〉を渡す
  -->
[後] 『受理する？』に常停止で答える機械は作れない

仕組み（言葉）: 判定器があると仮定→対角機械で矛盾。

試験での答え方: 定義を集合で書き『判定不可能』と結論。

停止問題 HALTTM（ていしもんだい）とは、

HALTTM={〈M,w〉| Mは入力wで停止する}。これも判定不可能。

別名: halting problem。講義では ATM を受理問題、こちらを真の停止問題と呼ぶ流れ。

なぜ出るか: 第11回。ATM→HALTTM の帰着が定番答案。

[前] 動かし続ける？止まる？
  -->
[後] 一般には判定できない

仕組み（言葉）: 停止判定ができれば受理判定に流用できる→矛盾。

試験での答え方: 帰着の矢印 ATM ≤ HALTTM を答案に書く。

帰着（きちゃく）とは、

問題Aを解くために問題Bの解法を部品として使う変換。判定不可能性の伝播に使う。

別名: reduction / 還元。

なぜ出るか: 『Aが判定不可能で A≤B なら Bも判定不可能』が第11–12回の型。

[前] Aの入力
  --> 変換
[後] Bの入力 → Bの答え → Aの答え

仕組み（言葉）: Bが易しいと仮定するとAも易しくなってしまう、を示す。

試験での答え方: 変換手順を番号付きで書き、矛盾を結論する。

Riceの定理（らいすのていり）とは、

TMが認識する言語についての、非自明な性質はすべて判定不可能、という一般定理。

別名: Rice’s theorem。

なぜ出るか: 第12回。『正規言語か？』『空か？』などを個別に帰着しなくても一括で説明できる。

[前] 『L(M)は性質Pを持つ？』
  -->
[後] Pが非自明なら判定不可能

仕組み（言葉）: 非自明＝いくつかのTMでは成り立ち、すべてでは成り立たない。

試験での答え方: 定理名＋『非自明な言語性質は判定不可能』。

対角線論法（たいかくせんろんぽう）とは、

可算と仮定した表の対角成分をずらして、表に無い要素を作り矛盾する証明技法。

別名: diagonal argument / Cantor の対角化。

なぜ出るか: 第10回。実数の非可算→言語の非可算→認識不能言語の存在。

[前] 行=番号, 列=桁の表
  -->
[後] 対角と全部違う x を作る → 対応漏れ

仕組み（言葉）: 『全部並べたつもり』のリストから、必ず漏れる1つを構成する。

試験での答え方: 仮定→対角要素の構成→矛盾、の3段で書く。

可算・非可算（かさん・ひかさん）とは、

可算=自然数と1対1対応できる。非可算=それができない（実数・全言語集合など）。

別名: countable / uncountable。

なぜ出るか: 『TMは可算、言語は非可算⇒認識できない言語がある』の前提。

[前] 1,2,3,… と並べられる
  -->
[後] 並べ切れない（実数・全言語）

仕組み（言葉）: 符号化できれば可算。対角化で非可算を示す。

試験での答え方: 定義を書き、TM符号化と特性列の議論へつなぐ。

線形境界付きオートマトン LBA（せんけいきょうかいつきおーとまとん）とは、

テープ使用量が入力長の定数倍までに制限されたTM。

別名: linear bounded automaton / 線形拘束オートマトン。

なぜ出るか: 第13–14回。ALBAは判定可能（状況数が有限でループ検出）。

[前] 普通のTM（テープ無限）
  -->
[後] LBA（使えるマスが入力長のO(1)倍）

仕組み（言葉）: 状況数が有限⇒十分回せば停止かループが分かる。

試験での答え方: 定義＋『ALBAは判定可能』をセットで書く。

計算履歴（けいさんりれき）とは、

入力に対する計算状況の列。受理計算履歴は開始から受理まで正当につながる列。

別名: computation history。

なぜ出るか: 第13–14回の帰着技法。『存在を問う問題』を履歴の存在に翻訳する。

[前] C0 → C1 → C2 → … → 受理
  -->
[後] この列全体が『証拠』

仕組み（言葉）: 停止しない計算には受理/拒否履歴が存在しない。

試験での答え方: 定義を列として書き、帰着でどう使うかを1文添える。

補Turing認識可能（ほちゅーりんぐにんしきかのう）とは、

補集合が Turing認識可能である言語のクラス。

別名: co-RE / co-Turing-recognizable。

なぜ出るか: 『認識可能かつ補認識可能⇔判定可能』。ATMの補は認識不可能。

[前] A を認識
  -->
[後] A̅ も認識 ⇒ 並列に回せば判定できる

仕組み（言葉）: 2台を並列シミュレーションし、先に受理した方で決める。

試験での答え方: 定理を述べ、ATM̅ が認識不可能である帰結を書く。

空テープ記号 ⊔（くうてーぷきごう）とは、

テープ上の『何も書いていない』を表す特別な記号。入力アルファベットには通常含めない。

別名: blank / 空白記号。

なぜ出るか: TM問題で入力の右端検出や消去に必ず出る。

[前] … X X X ⊔ ⊔ …
          ↑ヘッド
[後] ⊔ を読んだら『入力終わり』と解釈できる

仕組み（言葉）: 書き込んで消す・戻る、の目印。

試験での答え方: Γ の要素であり Σ には通常入らない、と区別して書く。

期末の作文・レポート型問題とは、

文献の一文を素材に、著者の考え・自分の賛否・根拠・引用意図を1000字前後で書く問題。

別名: 論述 / 生成AI利用指定がある年もある。

なぜ出るか: 中間・期末とも出る。選択・TMと並ぶ配点ブロック。

[前] 引用文
  --> 要約 → 賛否 → 根拠 → 文献
[後] 採点者が追跡できる答案

仕組み（言葉）: 『感想』ではなく『主張と根拠の対応』が本体。

試験での答え方: 主張1文→根拠→文献（どの記述か）の順。字数目安を守る。

基本情報のトレース問題（きほんじょうほうのとれーす）とは、

オートマトン・スタック・リストなど、状態を1手ずつ更新して選択肢を選ぶ問題。

別名: FE過去問枠（期末問4）。

なぜ出るか: 計算理論の用語と直結する外部問題がそのまま出る想定。

[前] 初期状態
  --> 入力1つ処理
[後] 次状態・出力・スタック頂を更新

仕組み（言葉）: 飛ばさず表を書く。途中省略が最大の失点源。

試験での答え方: 途中表を答案に残し、最終形と選択肢記号を書く。

個数の剰余を書くTM（こすうのじょうよをかくTM）とは、

入力記号の個数を mod 3 で数え、余りを左端に書いて他を空白にする変換機械。

別名: 期末2025問2型。

なぜ出るか: 期末の記述本線。状態=余り、終了時に左へ掃除して書く。

[前] XXXXX（5個）
  --> 数えながら右へ
[後] 左端に 2、他は ⊔

仕組み（言葉）: 右進で余りを状態に保持→空白で折り返し→左進で消去→答えを書いて停止。

試験での答え方: 空欄は『今の余り』と『折り返し後の掃除』で埋める。

ビットローテートTM（びっとろーてーとTM）とは、

列を1ビット右に回し、はみ出しを左端へ戻す変換を行うTM（中間2025問2型）。

別名: 1ビット右ローテート。

なぜ出るか: 中間過去問。期末も同型の『保持ビットを状態に載せる』が出る想定。

[前] 01011
  -->
[後] 10101

仕組み（言葉）: 先頭を覚え、右へシフトし、右端で折り返して左端に書く。

試験での答え方: 保持0/1で状態を分け、空欄を導出する。

空言語問題 ETM（くうげんごもんだい）とは、

ETM={〈M〉| L(M)=∅}。TMが何も受理しないかの判定。判定不可能。

別名: emptiness problem for TM。

なぜ出るか: 第12回の帰着例。ATMから変形機械を作る定番。

[前] 〈M,w〉
  --> M1 を作る（w以外拒否など）
[後] L(M1)=∅? の答え → 受理判定

仕組み（言葉）: 空かどうかが分かると受理問題が解けてしまう。

試験での答え方: 帰着構成を手順で書き判定不可能と結論。

出力付きオートマトン（Mealy）（めーりーきかい）とは、

遷移するときに入力だけでなく出力記号も出すオートマトン。辺ラベルは入力/出力。

別名: Mealy machine。FE問で頻出。

なぜ出るか: 期末過去問のFE枠。計算理論の遷移図読解と同一スキル。

[前] 状態 S —1/0→ 状態 T
  -->
[後] 入力1を読んだら出力0を出しTへ

仕組み（言葉）: 1入力ごとに1出力。出力列の長さ=入力長。

試験での答え方: 初期状態からトレース表を書き出力列を答える。

スタック（すたっく）とは、

後から入れたデータから出す（LIFO）データ構造。PDAのメモリ。

別名: 積み重ね / LIFO。

なぜ出るか: FEのPUSH/POP追跡。PDA理解の具体物。

[前] PUSH 1, PUSH 5, POP
  -->
[後] 頂は1（5が取り出された）

仕組み（言葉）: いじれるのは常に一番上だけ。

試験での答え方: 各操作後の列を書き、最終の底→頂を図示。

配列によるリスト（はいれつによるりすと）とは、

値配列とnext配列の対で連結リストを表す実装。挿入はポインタ（添字）書き換え。

別名: カーソル実装 / FEリスト問題。

なぜ出るか: 期末FE枠。『何番を差し込むと next[i] は幾つ』。

[前] A→E→C→G→B
  --> CとGの間にH
[後] C→H→G→B

仕組み（言葉）: 新要素のnextを旧nextに、前要素のnextを新要素へ。

試験での答え方: 現リストを辿り、挿入後の next を計算する。

形式定義 — 可算と特性列

集合 \(A\) が有限、または自然数 \(\mathbb{N}\) と1対1対応できるとき 可算。

アルファベット \(\Sigma\) 上の全言語の集合 \(\mathcal{L}\) は、無限二進列の集合 \(\mathcal{B}\) と対応する（言語 \(A\) の特性列 \(\chi_A\)）。\(\mathcal{B}\) は対角化で非可算 ⇒ \(\mathcal{L}\) も非可算。

一方、各TMは文字列に符号化できるのでTM全体は可算。よって どのTMでも認識されない言語が存在する。

例題【問】対角線論法（実数）

与え: \(\mathbb{N}\) と実数全体 \(\mathbb{R}\) の間に対応 \(f\) があると仮定する。求めよ: 矛盾の導き方（対角実数 \(x\) の構成方針）。

なぜ今この計算か: 非可算を示さないと『認識不能言語の存在』へ進めない。試験では構成手順を書く。

1. 対応 \(f:\mathbb{N}\to\mathbb{R}\) が全単射だと仮定する。
2. \(x\in(0,1)\) を小数で作る。第 \(n\) 桁は \(f(n)\) の小数第 \(n\) 桁と異なる値にする（0,9以外）。
3. 任意の \(n\) で \(x\neq f(n)\)（第 \(n\) 桁が違う）。よって \(x\) は対応に現れない。
4. 全射であることに矛盾。ゆえに \(\mathbb{R}\) は非可算。

答案文: 仮定した対応の対角をずらした実数を構成すると、どの自然数とも対にならないため矛盾する。よって実数全体は非可算である。

部分点: 仮定の明示 / 対角桁のずらし方 / 0と9を避ける注意 / 矛盾の結論 で配点されやすい

考察: 数値のどこを見るか: 『第n桁だけ』を変えれば、その行の実数全体と不一致になる点が本質。

形式定義 — ATM と判定不可能性

\(A_{\mathrm{TM}}=\{\langle M,w\rangle\mid M\text{ はTM，}M\text{ は }w\text{ を受理}\}\)。

判定装置 \(H\) があると仮定すると、対角機械 \(D\) を『\(H(\langle M,\langle M\rangle)\) が受理なら拒否、拒否なら受理』と作れ、\(D(\langle D\rangle)\) で矛盾する。

例題【問】ATM が判定不可能であることの骨格

与え: ATM に対する判定装置 H が存在すると仮定する。求めよ: 矛盾を導く対角機械 D の動作と、結論。

なぜ今この計算か: 期末の選択でも『決定不能』の意味を聞かれ、記述でも帰着の出発点になる。

1. H は任意の 〈M,w〉 に対し停止して受理/拒否を返すと仮定。
2. D を構成: 入力 〈M〉 に対し H〈M,〈M〉〉 を実行し、受理なら拒否、拒否なら受理。
3. D〈D〉 を考える。H〈D,〈D〉〉 が受理 ⇔ D が 〈D〉 を受理、だが D の定義よりこのとき拒否する → 矛盾。
4. 拒否側も同様に矛盾。ゆえに H は存在しない。ATM は判定不可能。

答案文: 判定装置を仮定すると自分自身の記述で矛盾する対角機械が構成できるため、ATMは判定不可能である。

部分点: 仮定 / Dの定義 / D〈D〉の矛盾 / 結論 の4点が部分点の柱

考察: 数値というより記号 〈D〉 を『自分で自分を入力』に使う場所が採点ポイント。

例題【問】ATM から HALTTM への帰着

与え: HALTTM が判定可能と仮定する。求めよ: その仮定で ATM を判定する手順を書き、矛盾を述べよ。

なぜ今この計算か: 『すでに判定不可能なものからの帰着』が第11回以降の答案テンプレ。

1. R が HALTTM を判定すると仮定。
2. 〈M,w〉 が来たら、M が w を受理するときだけ停止受理し、そうでなければループする（または拒否をループに変える）機械 M1 を構成する。
3. R〈M1,w〉 が停止するなら M は w を受理、しないなら非受理、と読む（講義スライドの変形に正確に合わせる）。
4. これで ATM が判定できてしまう → ATM 判定不可能に矛盾。ゆえに HALTTM も判定不可能。

答案文: HALTTMが判定可能ならATMも判定可能となって矛盾するため、HALTTMは判定不可能である。

部分点: 帰着の方向（何を何へ） / 変形機械 / 矛盾の一文

考察: 答えの核は『停止判定ができれば受理判定に流用できる』という依存の向き。

例題【問】ETM の判定不可能性（骨格）

与え: ETM={〈M〉| L(M)=∅}。求めよ: ATM からの帰着で判定不可能であることを示す答案の骨格。

なぜ今この計算か: Rice に行く前の『個別帰着』練習。空言語判定が解けたら受理判定も解けてしまう。

1. ETM 判定器 R を仮定。
2. 〈M,w〉 から M1 を作る: 『入力 x が w と異なるなら拒否。等しいなら M(w) をシミュレート』。
3. すると L(M1)=∅ ⇔ M が w を受理しない。
4. R〈M1〉 の答で ATM が判定できる → 矛盾。ETM は判定不可能。

答案文: ATMをETMへ帰着できるため、ETMは判定不可能である。

部分点: M1の仕様 / 空⇔非受理の対応 / 結論

考察: 対応関係『L(M1)=∅ ⇔ 非受理』を答案に明示すると点が安定する。

例題【問】Rice の定理の使い方

与え: 『与えられたTMの言語が正規言語か？』を判定する問題。求めよ: Riceの定理を用いた結論と、非自明性の確認方針。

なぜ今この計算か: 個別帰着を全部書く時間がないときの一般定理。

1. 性質P: 『L(M) は正規』。これは言語の性質（同じ言語なら同じ真偽）。
2. 非自明: 正規言語を認識するTMも、非正規を認識するTMもある。
3. よって Rice より P は判定不可能。
4. （必要なら）正規の例 Σ*、非正規の例 {0^n1^n} を一文添える。

答案文: 『L(M)が正規か』は非自明な言語性質なので、Riceの定理より判定不可能である。

部分点: 性質の記述 / 非自明の例 / 定理名

考察: 『機械の見た目』ではなく『言語の性質』であることが適用条件。

形式定義 — LBA と状況数

LBA はテープ長が入力長 n の定数倍に抑えられたTM。状態数 q、テープ記号種 g のとき、長さ n 入力に対する異なる計算状況は高々 \(q\cdot n\cdot g^{O(n)}\) 個（講義の補題5.8の形）。

よって十分長いステップ走らせて停止しなければ状況の繰り返し＝ループと判定できる ⇒ A_LBA は判定可能。

例題【問】A_LBA が判定可能な理由

与え: LBA M と入力 w（|w|=n）。求めよ: M が w を受理するか判定するアルゴリズムの骨格と、停止する根拠。

なぜ今この計算か: TMの受理は判定不可能、LBAは可能な対比が試験で問われやすい。

1. 状況数の上界 N を補題から取る。
2. M を w 上で最大 N ステップまでシミュレートする。
3. その前に受理停止 → 受理。拒否停止 → 拒否。
4. N ステップ超えても停止しない → 状況繰り返しが不可避 → ループとみなし拒否（非受理）。

答案文: LBAの計算状況は入力長に対し有限個しかないので、十分なステップのシミュレーションで受理の可否を判定できる。

部分点: 状況有限 / シミュレーション / ループ⇒非受理

考察: 数 N を暗記するより『有限だから鳩の巣でループが分かる』が答案の核。

例題【問】受理計算履歴の定義確認

与え: TM M と入力 w。求めよ: 『w に対する受理計算履歴』を定義し、M が停止しない場合にそれが存在するか答えよ。

なぜ今この計算か: 第13–14回の帰着は履歴の存在命題への翻訳が多い。

1. C0 は初期状況（開始状態・ヘッド位置・テープ内容）。
2. 各 Ci から Ci+1 は遷移関数に従う正当な1ステップ。
3. Ck は受理状況。
4. M が w で停止しないなら受理/拒否履歴は存在しない。

答案文: 受理計算履歴とは開始から受理までの正当な計算状況列であり、停止しない計算には存在しない。

部分点: 列の条件3つ / 非停止⇒非存在

考察: 『履歴＝証拠』と覚えると帰着問題で使いやすい。

形式定義 — 包含と『必ず存在する』

正規言語 ⊂ 文脈自由言語 ⊂ … ⊂ 句構造言語。計算モデルでは FA ⊂ PDA ⊂ TM（認識能力）。

言語 L を認識する FA がある ⇒ L は正規 ⇒ 正規文法が存在し、TM（やプログラム）でも認識できる。

例題【問】期末型選択（階層）

与え: 言語Lを認識する有限オートマトンが存在する。求めよ: 次のうち必ず存在するものをすべて選べ。
a. Lを生成する文脈自由文法 b. Lを生成する正規文法 c. Lを認識するコンピュータのプログラム d. Lを認識するチューリング機械

なぜ今この計算か: 2025期末問1(1)と同型。包含の向きを一回でも手で使う。

1. FAがある ⇒ L は正規言語。
2. 正規言語 ⇒ 正規文法が存在する → b。
3. 正規 ⊂ 文脈自由 ⇒ 文脈自由文法も存在する → a。
4. TMはFAをシミュレート可能 → d。プログラムも同様 → c。
5. よって a,b,c,d すべて。

答案文: FAが存在する言語は正規なので正規文法・文脈自由文法・TM・プログラムがいずれも存在する。

部分点: 正規の指摘 / 各選択肢の根拠1行

考察: 『複数正解は全部』を見落とすと一気に失点する。

例題【問】文法記号の所属

与え: G=(N,T,P,A), N={A,B}, T={a,b}, P={A→aaa, A→ε, B→bb}。求めよ: 正しい記述をすべて選べ。
a. Aは非終端かつ開始記号 b. εは非終端記号 c. Gは正規文法 d. Gは文脈（自由）文法

なぜ今この計算か: 2025期末問1(4)と同型。εの扱いがひっかけ。

1. A∈N かつ開始記号 → a は正しい。
2. ε は空列であり非終端ではない → b は誤り。
3. A→aaa は右辺に終端のみで非終端が無い（正規の一種になり得る）が、正規文法の定義（右線形等）と照合。A→aaa は右線形（A→a a a）として正規側、B→bb も同様。ただし講義定義に厳密準拠。
4. 左辺が単一非終端なので文脈自由文法 → d 方向は正しい（『文脈文法』表記は講義の選択肢に合わせる）。
5. 答案では a と、講義選択肢の正誤に合わせ d（および正規判定）を明記。2025正答は a（と講義解答準拠）。

答案文: Aは非終端かつ開始記号である。εは非終端記号ではない。

部分点: 四つ組の読み / εの否定 / 規則形

考察: 選択肢の『文脈文法』が文脈自由を指すか文脈依存を指すか、講義表記に合わせること。

例題【問】決定不能の定義

与え: 『決定不能問題とは』の選択肢。求めよ: 正しいものを選べ。
a. yes/noで答えられない b. この世に一つしかない c. 何が問題かわからない d. 問題を解く手順が存在しない

なぜ今この計算か: 期末問1(3)。感覚語に引っ張られない。

1. a は『主観で答えられない』に読め誤解。決定問題は yes/no 問題だが不能とは別。
2. b,c は定義でない。
3. d が定義に一致。

答案文: 決定不能問題とは、問題を解く手順が存在しない問題である。

部分点: 定義の言い換え一致

考察: 『わからない』ではなく『手順が無い』がキーワード。

形式定義 — 余りを状態に載せる

入力は X の列。出力は |X| mod 3 ∈ {0,1,2} を左端に書き、他セルは ⊔、ヘッドは左端、受理停止。

状態 q0,q1,q2,q3 で右進カウント（q3≃ちょうど3の倍数を読み終えた）、q1L/q2L/q3L で左進掃除。

例題【問】Xが4個のときのトレース

与え: テープ XXXX（左端から）。求めよ: 最終テープ（左端の記号）と、余りに対応する左進状態。

なぜ今この計算か: 空欄を埋める前に『4≡1 (mod 3) → 左端に1』をトレースで固定する。

1. 右進で X を数え、空白に当たったときの余り状態を見る（4個目の後は余り1）。
2. 余り1なら q1L で左へ戻り、途中の X を ⊔ に消す。
3. 左端の ⊔ で 1 を書いて qf,S。
4. 検算: 3個なら0、5個なら2。

答案文: Xが4個のとき 4≡1 (mod 3) なので左端に1を書き受理停止する。

部分点: mod計算 / 対応するL状態 / 最終テープ形

考察: 数値4を見て『1を書く』と即決できるかが部分点の入口。

形式定義 — 右ローテート

Γ={0,1,⊔}, Σ={0,1}。入力を1ビット右ローテートし、ヘッドを左端、受理停止。

例: 01011→10101。保持ビットを状態 q0/q1 に載せ、戻りは q2/q3。

例題【問】01011 のローテートトレース要点

与え: 入力 01011。求めよ: 出力列と、『右端で保持1のとき戻る状態』。

なぜ今この計算か: 中間問2の公式例。保持と戻り状態の対応を身体で覚える。

1. 先頭ビットを状態に保持しつつ右へコピーシフト。
2. 右端 ⊔ で折り返し。保持が1なら q3 系で戻る。
3. 左端 ⊔ に保持ビットを書いて受理。
4. 出力は 10101。

答案文: 01011 を1ビット右ローテートすると 10101 になる。

部分点: 出力例 / 保持と状態の対応

考察: 例の数値 01011→10101 を暗記するより、保持ビットの更新規則を書く。

形式 — 採点される段落構成

1. 著者の主張を自分の言葉で1–2文
2. 賛否を明示
3. 根拠（計算モデル／AI／経験のどれか）を具体的に
4. 文献は『どの記述とどうつながるか』まで書く
5. 字数目安（期末は1000字以内など）を守る

例題【問】賛否アウトラインを作れ

与え: 『コンピュータは自分で考えることはできない』（高岡）。求めよ: 950字以上を想定した段落見出しと、各段落で書く一文メモ。

なぜ今この計算か: 本文をいきなり書くと引用意図が消える。先に骨組み。

1. ①主張: 判断に見えても規則に従う処理にすぎない、と要約。
2. ②賛否: おおむね賛成、と宣言。
3. ③根拠A: TMは遷移の機械的適用である点。
4. ④根拠B: 中国語の部屋など『操作≠理解』（文献接続を明記）。
5. ⑤結論: 予測はできても主体的思考ではない、と締める。

答案文: 著者の主張を要約したうえで賛否を明示し、計算モデルと文献を根拠に結論づける。

部分点: 賛否の明示 / 文献の意図 / 字数

考察: 採点者が追うのは『文献のどの文が自分のどの文を支えているか』。

例題【問】Mealy 出力トレース

与え: 初期状態S1。遷移は 0/0,1/0（S1）、0/0,1/1（S2）、0/0,1/1（S3）型（期末FE図）。入力 0011001110。求めよ: 出力列。

なぜ今この計算か: 辺ラベル『入力/出力』を1手ずつ確定する練習。

1. S1で0→出力0のままS1。同様にもう一度0→0。
2. 1→S2/出力0。次の1→S3/出力1。
3. 0→S1/0。0→S1/0。
4. 1→S2/0。1→S3/1。1→S3/1。0→S1/0。
5. 出力列 0001000110。

答案文: 入力0011001110に対する出力は0001000110である。

部分点: 途中状態表 / 最終列

考察: 出力の4ビット目が1になる位置（連続1の2つ目）を見ると検算しやすい。

例題【問】スタック操作後の状態

与え: 空スタックに PUSH1→PUSH5→POP→PUSH7→PUSH6→PUSH4→POP→POP→PUSH3。求めよ: 底から頂の並び。

なぜ今この計算か: LIFOを飛ばさず書く。FE図選択肢と照合。

1. [] →[1]→[1,5]→[1]→[1,7]→[1,7,6]→[1,7,6,4]
2. POP→[1,7,6] / POP→[1,7] / PUSH3→[1,7,3]
3. 底が1、中が7、頂が3。

答案文: 最終的に底から1,7,3となる。

部分点: 各POP後の頂 / 最終3つ

考察: 頂が3、その下が7かを図で確認する。

例題【問】リスト挿入後の next[8]

与え: next[0]=1 で A→E→C→G→B。Hは添字8にあり未連結。3番目と4番目の間にHを挿入。求めよ: next[8]。

なぜ今この計算か: ポインタ更新は『新next←旧next、前next←新』。

1. リストを辿り3番目が index3（C）、4番目が index7（G）と確認。
2. Hは index8。挿入後は C の次が8、8の次が旧4番目7。
3. よって next[8]=7。

答案文: 挿入後、next[8] は元の4番目である7を指す。

部分点: 3/4番目の特定 / next[8]の値

考察: 聞かれているのが next[8] であり next[3] ではない点に注意。

解答例【問1】選択

与え: 上記(1)～(4)。求めよ: 各小問の正解記号（複数は列挙）。

なぜ今この計算か: 本番同型。根拠を1行ずつ残す。

1. (1) FAあり⇒正規⇒正規文法・CFG・TM・プログラムすべて存在 → a,b,c,d
2. (2) a,b,c が階層として正しい。d（決定不能問題∈句構造言語）はカテゴリ混同で不適切 → a,b,c
3. (3) 定義は d
4. (4) a は正しい。b は誤り（εは空列）。c/d は規則形と講義用語に依存だが、最低限 a を落とさない

答案文: 各小問について包含関係または定義に照らして正しい記号を列挙する。

部分点: 小問ごと。複数正解の取りこぼしに注意

考察: (3)で『答えられない』を選ぶと定義ずれ。(4)でεを非終端にすると即失点。

解答例【問2】空欄①～⑩

与え: 上記δの空欄。求めよ: ①～⑩に入る記号。

なぜ今この計算か: 期末記述の本線。保持（余り）と折り返しを言葉で固定してから埋める。

1. ① は右へ進むので R
2. ② は q2（q2 で X を見て q3 へ）
3. ③ は X（カウント中は記号を残し、掃除は*Lに任せる）
4. ④ は q3L（ちょうど3の倍数で空白→0を書く系へ）
5. ⑤ は L（消去しながら左へ）
6. ⑥ は S（1を書いて停止）
7. ⑦ は q2L
8. ⑧ は 2
9. ⑨ は L
10. ⑩ は qf

答案文: 余りを状態に載せ、空白で折り返して左端に 0/1/2 を書く遷移で空欄を埋める。

部分点: ①④⑧⑩など定義直結箇所 / ②⑦の状態対応

考察: 検算: X1個→1、X2→2、X3→0。数値と書く数字が一致するか見る。

解答例【問3】答案の骨組み（全文は自筆）

与え: 上記作文課題。求めよ: 採点に耐える段落構成と、各段落の要旨（実際の提出文は自分の言葉で950字以上を目安に書く）。

なぜ今この計算か: 模範全文の丸写しは学習効果が薄い。型を固定する。

1. 著者: 判断に見えてもプログラムされた計算であり自発的思考ではない、と要約。
2. 賛否: 賛成（または条件付き賛成）を明示。
3. 根拠: TM/アルゴリズムは規則適用であること。生成AIも最適化であり『意味の理解』とは別、と具体化。
4. 文献: Searle 1980 等を用いるなら『シンボル操作≠理解』のどの論点が自分の賛否を支えるかを1文で接続。
5. 結論: 予測・判断はできても主体的思考とは言えない、と字数内で締める。

答案文: 著者の主張を要約し賛否と根拠を示し、文献の意図が読める形で結論づける。

部分点: 賛否明示 / 根拠の具体 / 引用意図

考察: 課題PDFが指摘する『引用の意図不明』を避けるのが最大の加点ポイント。

解答例【FE問4】Mealy

与え: 図のオートマトンと入力0011001110。求めよ: 出力列と選択肢。

なぜ今この計算か: 過去問図の完全トレース。

1. S1から1記号ずつ遷移し出力を記録（本編§FEの表と同じ）。
2. 出力 0001000110 → ア

答案文: 出力記号列は0001000110である。

部分点: 途中表 / 選択肢

考察: 4ビット目が1になる位置で検算。

解答例【FE問5】スタック

与え: PUSH1→…→PUSH3 の列。求めよ: 最終スタック図の選択肢。

なぜ今この計算か: LIFOの手計算。

1. 操作を追い [1,7,3]（底→頂）
2. 図ウ（頂3・中7・底1）

答案文: 最終状態は底から1,7,3である。

部分点: 最終3要素

考察: 頂が3かで選択肢が分かれる。

解答例【FE問6】リスト挿入

与え: 図の配列。Hを3–4番目間に挿入。求めよ: next[8]。

なぜ今この計算か: ポインタ更新。

1. 3番目C(index3), 4番目G(index7)
2. next[8]=7 → ウ

答案文: next[8]の値は7である。

部分点: 3/4番目特定 / 数値7

考察: next[3]の更新と取り違えない。

解答例【中間問1】

与え: 上記(1)～(4)。求めよ: 正解記号。

なぜ今この計算か: 定義の正確さチェック。期末選択のウォームアップ。

1. (1) c（初期ヘッドは左端。a,b,dは定義に反しうる）
2. (2) a,b,c,d（認識にも変換にも使え、FA/PDAより強い）
3. (3) 講義のδトレースで奇数本の a → 対応する選択肢
4. (4) c メモリ

答案文: TMの定義に照らして正しい記述を列挙する。

部分点: 小問ごと

考察: (1)で『受理時は必ず⊔』を選ぶと定義オーバー。

解答例【中間問2】空欄の核

与え: 右ローテートTMの空欄。求めよ: 特に保持ビット更新に関わる空欄の値。

なぜ今この計算か: trace-spec（theory-calculation-h1-past）と整合する核だけを期末対策で再掲。

1. 先頭を読んで保持状態へ（①は1など）
2. 右進で書き換え、右端で L へ折り返し
3. 保持1の戻りは q3、保持0は q2
4. 公式例 01011→10101 でトレース検算

答案文: 保持ビットの更新規則に従い空欄を埋める。

部分点: ④⑥⑨

考察: 禁止されがちな誤答（④=q1等）は意味論で落とす。

解答例【中間問3】進め方

与え: 上記3-1～3-4。求めよ: 提出物チェックリスト。

なぜ今この計算か: 期末作文より手順が多い。抜けを防ぐ。

1. 3-1: AI本文を貼る（字数）
2. 3-2: ツール名とプロンプト全文
3. 3-3: (a)(b)(c)を別々に200字
4. 3-4: 文献1つ以上＋自分の経験を入れて1000字

答案文: 指定の小問を欠けなくそろえる。

部分点: 小問ごと

考察: 3-3(c)が3-4の核になる。

L4【solo】Xが7個のとき左端に書く数字

与え: XXXXXXX（7個）。求めよ: 左端に書く記号。本編の4個例とは別数値。

L4【fade】1101 の右ローテート

与え: 1101。求めよ: 1ビット右ローテート後の列（01011例とは別）。

L4【solo】Mealy 入力 11010

与え: 本編と同じ遷移図。入力 11010（0011001110とは別）。求めよ: 出力5ビット。

L4【solo】別操作列のスタック

与え: 空から PUSH2→PUSH9→POP→PUSH4→PUSH8→POP→PUSH5。求めよ: 底→頂。

L4【fade】包含の向き

与え: 『文脈自由言語は句構造言語を包含する』は真か偽か。本編選択とは別サーフェス。

L4【solo】対角機械の一言説明

与え: HがATM判定器と仮定。求めよ: D〈M〉の動作を2文で述べよ（本編と別表現）。