Author#

KardeniaPoyu

Description#

(1) 図1に示す ANSI-C 準拠である C 言語のプログラム (program) は, 重複のない N (自然数, $1 \le N \le 2000$ とする) 個の整数を昇順に配列 (array) A の要素 A[1]～A[N] に格納し, 変数 x の値が配列 A の要素に含まれているかどうかを2分探索法 (binary search) を用いて探索するプログラムである. このプログラムは, 探索の途中経過と, x の値が配列 A の要素に含まれる場合はその値が格納されている配列 A のインデックス (index), x の値が配列 A の要素に含まれない場合は 0 を出力する. N の値の設定, 配列 A[1]～A[N] に整数値を設定する処理, 変数 x の値を設定する処理, 及び, これらの値が妥当かどうかを確認する処理は省略している. 以下の各小問に答えよ.

(1-1) 図1のプログラムに対して, N, A[1]～A[N], x を下記のように設定した時の出力結果を書け. N=8, A[1]=2, A[2]=5, A[3]=8, A[4]=10, A[5]=15, A[6]=20, A[7]=25, A[8]=30, x=8

(1-2) N=1000 で, x の値が A[1]～A[N] のどこかに存在する場合, 図1中の do-while ループが実行される回数は最大何回か. その理由も簡潔に説明せよ.

(1-3) 図1 の do-while ループ中の $\Box$ で囲われた部分を下記のように変更する.

変更前

1
if (A[mid] < x) left = mid+1;
2
else            right= mid-1;

変更後

1
if (A[mid] < x) left = mid;
2
else            right= mid;

変更前のプログラムは正しく結果が出力されるが, 変更後のプログラムは正しく結果が出力されないことがある. そのような N, A[1]～A[N], x の設定例を一つあげ, 「正しく結果が出力されない」状況がどのようなものかを簡潔に説明せよ.

1
#include <stdio.h>
2
/* この部分でNの値が設定される. */
3
int main(void)
4
{
5
    int A[N+1];
6
    int mid, left, right, x, index;
7
/* この部分に下記の処理が記述されているとする.
8
   ・配列A[1]～A[N]の値が設定される.
9
   ・変数xに探索すべき値が設定される.
10
   ・配列A[1]～A[N], xの値が妥当かどうか確認される.
11
*/
12
    left = 1;
13
    right = N;
14
    do {
15
        mid= (left+right)/2;
16
        printf("%d %d %d\n",left,mid,right);
17
        if (A[mid]<x) left = mid+1;
18
        else          right= mid-1;
19
    } while (A[mid] != x && left <= right);
20
    if (A[mid]==x) index=mid;
21
    else           index=0;
22
    printf("%d\n", index);
23
    return 0;
24
}

(2) 図2に示す ANSI-C 準拠である C 言語のプログラム (program) は, 0-1 ナップサック問題 (0-1 knapsack problem) の解を求めて表示するプログラムである. なお, 図の左端の数値は行番号を表す. 0-1 ナップサック問題は, ある容量 (capacity) のナップサックが一つと, それぞれ大きさ (size) と価値 (value) が定められた複数の品物が与えられた時, ナップサックの容量を超えない範囲で価値の和が最大となる品物の組み合わせを求める問題である. 本プログラムでは, 四つの品物のそれぞれに他と重複しない番号が与えられており, 番号 i ($1 \le i \le 4$) の品物の大きさと価値が, 配列 size の要素 size[i] と配列 value の要素 value[i] としてそれぞれ格納されている. なお, 各番号の品物はそれぞれ一つしかなく, また, 分割できない. 品物の大きさと価値は自然数とする. 以下の各小問に答えよ.

(2-1) 22 行目の処理を実行する直前の配列 sack の内容を, 解答用紙の表の空欄を埋めることにより答えよ.

(2-2) 図2のプログラム中の空欄 (ア), (イ) を適切な式 (expression) で埋めよ.

1
#include <stdio.h>
2
#define capacity 15     /* ナップサックの容量 */
3
#define item 4          /* 品物の個数 */
4
int main(void) {
5
  int size[] = {0, 2, 6, 6, 2};
6
  int value[] = {0, 20, 30, 15, 25};
7
  int sack[item+1][capacity+1];
8
  int i, j, max, index;
9

10
  for (i = 0; i <= item; i++)
11
    for (j = 0; j <= capacity; j++)
12
      sack[i][j] = -1;  /* ナップサックの初期化 */
13
  sack[0][0] = 0;       /* 品物が入っていない(大きさの和が0)のナップサックの総価値は0 */
14

15
  for (i = 1; i <= item; i++)
16
    for (j = 0; j <= capacity; j++)
17
      if (sack[i-1][j] != -1) {
18
        if (sack[i-1][j] > sack[i][j]) sack[i][j] = sack[i-1][j];
19
        if (j + size[i] <= capacity) sack[i][j+size[i]] = sack[i-1][j] + value[i];
20
      }
21

22
  max = 0; index = 0;
23
  for (j = 0; j <= capacity; j++)
24
    if (sack[item][j] > max) {max = sack[item][j]; index = j;}
25
  for (i = item; i >= 1; i--)
26
    if (index >= size[i] &&         (ア)         ==        (イ)       ) {
27
      printf("item %d is in a knapsack\n",i);
28
      index = index - size[i];
29
    }
30
  return 0;
31
}

Kai#

1
1 4 8
2
1 2 3
3
3 3 3
4
3

Summary#

NOTE

模块一：算法与动态规划 (0-1 背包问题) 💡 核心思想：大问题拆成小问题，查表避免重复计算。

• 贪心算法的失效： 在不可分割的 0-1 背包中，按性价比（价值/重量）贪心会留下无法利用的空间缝隙，导致拿不到全局最优解。
• 状态转移方程（核心公式）： 面对第 $i$ 件物品、剩余容量 $j$ 时的最大价值： $DP[i][j] = \max(\text{不拿}, \text{拿})$ $DP[i][j] = \max(DP[i-1][j], DP[i-1][j - weight] + value)$
• 表格初始化： 起点 DP[0][0] = 0，其余无法到达的状态初始化为 -1（刷表法技巧，用于剪枝无效计算）。
• 回溯找物品（破案法）： 倒序遍历。如果 当前总价值 == 扣除该物品重量后的历史价值 + 该物品价值，说明该物品被选中。随后将背包当前重量减去该物品重量，继续往上追查。

Author#

KardeniaPoyu

Description#

(1) 浮動小数点数 (floating point number) に関する以下の小問に答えよ. なお x を 2進数 (binary number) として解釈する場合, $[x]_2$ と表記する. 角括弧 (square bracket) をつけない場合は 10進数と解釈する.

(1-1) 0.625 を 2進数として表記せよ.

(1-2) IEEE 754 で規定された半精度浮動小数点数表現 (representation of half precision floating point number) において, 以下の値に最も近い値を表すビット列を解答用紙に書け. (a) $[1.101]_2$ (b) 5 (c) 0.125 (d) 0.1

(1-3) 2進数の浮動小数点数表現では, 0.1 を誤差なく有限桁で表現できない理由を述べよ.

資料: IEEE 754 半精度浮動小数点数表現 簡略版 (simplified version)

符号部 (sign) を 1 ビット, 指数部 (exponent) を 5 ビット, 仮数部 (significand) を 10 ビットで表現. 指数部が表す符号無し整数を $e$, 仮数部のビット列を $f$ とすると, この形式が表す値は $(-1)^{\text{符号部}} \times 2^{e-15} \times [1.f]_2$ である. ただし, $e=0, 31$ の時は上式をあてはめない非正規化数 (special value) として扱う. 本問題では非正規化数を扱わないため, その説明を省略する.

(2) メモリ管理に関する以下の小問に答えよ. 解答は全て解答欄の太線内に書くこと.

(2-1) 計算機 (computer) においては, 読み書きの速度 (reading and writing speed), 容量 (capacity) が異なる複数種類の記憶素子 (memory device) や記憶装置 (memory unit) を連携動作させて, 高速な読み書きと大容量の両立を図る, 記憶階層 (memory hierarchy) の考え方が導入されている. 以下に示す記憶素子または記憶装置 (ア)～(オ) を有する一般的な計算機において, これらを, 読み書きが速く, 容量の少ない順に整列し, 記号で答えよ. (ア) 主記憶装置 (main memory unit), (イ) 2次キャッシュメモリ (secondary cache memory), (ウ) 補助記憶装置 (auxiliary memory unit), (エ) レジスタ (register), (オ) 1次キャッシュメモリ (primary cache memory)

(2-2) 以下の文章の空欄 (a)～(i) に当てはまる最も適切な語句を, 下記の選択肢から選び, 記号で答えよ. 同じ選択肢を複数回用いても良い.

記憶階層の一部を成す仮想記憶 (virtual memory) では, 主記憶装置に置くべきプログラムやデータ (以下では “情報” と呼ぶ) の一部を [ (a) ] に置く. これにより, 主記憶装置の持つアドレス空間よりもより広いアドレス空間を有するように, ユーザープログラムに見せかける効果がある. 機械語命令 (machine instruction) の中に記載されるアドレスは [ (b) ], アドレスバスに送出されるアドレスは [ (c) ] と呼ばれる. 仮想記憶において, 必要な情報が主記憶装置上に無く, [ (d) ] 上にある場合, この情報は主記憶装置に移動される. この動作は [ (e) ] と呼ばれる. この時, 主記憶装置上に空き領域が無ければ, 使用される可能性が低い情報が主記憶装置から [ (f) ] へ移動され, 空き領域が作られる. この動作は [ (g) ] と呼ばれる. [ (e) ] や [ (g) ] が頻繁に発生すると, 計算機の処理性能が低下する. 仮想記憶の代表的な実現方法として, メモリを固定長 (fixed size) のブロック (block) で管理する [ (h) ] 方式と, 可変長 (variable size) のブロックで管理する [ (i) ] 方式とがある.

【選択肢】

(2-3) ページ枠 (page frame) 数が 4 のページング方式を採用した仮想記憶を考える. 以下に示すページ番号 (仮想アドレス空間におけるページの番号) の順にメモリ参照が起こった時, ページ置換アルゴリズム (page replacement algorithm) が LRU (least recently used) 法と FIFO (first-in-first-out) 法のそれぞれについて, 主記憶装置上に置かれる各ページ枠が保持するページの番号を答えよ. なお, 初期状態では全てのページ枠は空であるとし, 解答欄に示されている前半の例を参考に, 後半の太線内について解答すること. また, ページフォルト (page fault) が発生する場合はページ番号を◯で囲むこと. 参照ページ番号 : 0, 1, 2, 3, 3, 4, 2, 1, 0, 5, 1, 2

(2-4) ページング方式を採用した仮想記憶を有する計算機で, 主記憶装置に入り切らないサイズの整数型配列 (array) A[W*H] を扱うプログラムを考える. 以下に示す C 言語で書かれた二つのプログラム断片 (ア), (イ) の内, その処理時間が短くなる方を選び, 記号で答えよ. また, その理由を仮想記憶と関連付けて説明せよ. なお, コンパイラ (compiler) による最適化は行われず, キャッシュメモリを有しない計算機で実行するものとする.

(ア)

1
for (x=0; x<W; x++) {
2
    for (y=0; y<H; y++) {
3
        sum = sum + x * A[x+(y*W)];
4
    }
5
}

(イ)

1
for (y=0; y<H; y++) {
2
    for (x=0; x<W; x++) {
3
        sum = sum + x * A[x+(y*W)];
4
    }
5
}

Kai#

Summary#

NOTE

模块二：数据表示与浮点数 (IEEE 754) 💡 核心思想：二进制的科学记数法与精度妥协。

• 十进制转二进制（双轨制）：
  • 整数部分： 除 2 取余法，一直算到商为 0，余数倒序排列（从下往上读）。
  • 小数部分： 乘 2 取整法，一直算到小数为 0，整数部分顺序排列（从上往下读）。
• 为什么 0.1 存不准？ 0.1 乘以 2 会陷入无限循环（0.2 $\rightarrow$ 0.4 $\rightarrow$ 0.8 $\rightarrow$ 1.6 $\rightarrow$ 1.2 $\rightarrow$ 0.2…），由于计算机位数有限，必须截断，必然导致精度丢失。
• IEEE 754 组装三要素（以半精度为例）：
  1. 符号位 (Sign)： 正数 0，负数 1。
  2. 指数部 (Exponent)： 实际指数 + 偏移量（Bias，题目中为 15）。
  3. 尾数部 (Significand)： 将二进制写成 $1.xxx$ 的科学记数法后，省略最前面的 1，只存小数点后面的 $xxx$，不够的位数补 0。

模块三：内存管理与操作系统 (OS) 💡 核心思想：用最便宜的硬件，造出最快、最大的内存假象。

• 存储器速度阶级（由快到慢）： 寄存器 (Register) $\rightarrow$ L1 缓存 $\rightarrow$ L2 缓存 $\rightarrow$ 主存 (内存条) $\rightarrow$ 辅助存储 (硬盘)。
• 虚拟内存与地址翻译：
  • 程序使用的是虚拟地址，主板认的是实地址（物理地址）。
  • 翻译官是 MMU (内存管理单元)，它还负责检查越界权限。
• 页面调度机制：
  • 缺页中断 (Page Fault)： CPU 发现数据不在内存中。
  • Swap in (换入)： 把数据从硬盘搬进内存。
  • Swap out (换出)： 内存满了，把旧数据踢回硬盘。
• 页面置换算法：
  • FIFO (先进先出)： 踢走最早进来的，死板。
  • LRU (最近最少使用)： 踢走最久没被访问过的，符合时间局部性，聪明。
• 内存碎片与切分方式：
  • 外部碎片 (Fragmentation)： 内存有总空闲，但都是不连续的小块，大程序塞不进去。
  • 分页 (Paging)： 按固定大小切块（如 4KB），完美解决外部碎片问题。
  • 分段 (Segmentation)： 按程序逻辑（可变长度）切块，容易产生碎片。

模块四：计组底层机制与硬件 💡 核心思想：代码的写法必须迎合底层的物理构造。

• 空间局部性与性能雪崩 (Thrashing)：
  • C 语言二维数组在物理内存中是按行连续存放的。
  • 内层循环遍历列 ($x$)： 地址连续，顺滑读取缓存，性能极佳。
  • 内层循环遍历行 ($y$)： 地址大跨度跳跃，疯狂触发缺页中断，导致系统抖动 (Thrashing)，卡死。
• 上下文切换 (Context Switch)： CPU 在不同进程间切换时，保存旧状态、加载新状态的过程，非常耗费性能。
• 直接映射缓存 (Direct Mapping)： 主存块只能放在缓存的固定槽位（主存号 % 槽位数）。优点是找得快，缺点是极易发生冲突（Cache Miss）。
• MAU 的双重含义：
  1. 内存访问单元（流水线里的搬运工）。
  2. 最小可寻址单元（通常是 1 Byte，即内存给数据打包的最小单位）。

使用建议： 你可以把这四个模块当成考纲。复习时遮住下面的解释，光看加粗的“核心思想”和“名词”，看自己能不能在脑子里或者草稿纸上复述出后面的逻辑。如果卡壳了，再回来查漏补缺！祝你复习顺利！

Author#

KardeniaPoyu

Description#

(1) 一階述語論理 (first-order predicate logic) に関する以下の各小問に答えよ. ただし, 一階述語論理式 (first-order predicate logic formula) の記述には以下の記号を用いる. $\forall, \exists$ はそれぞれ全称作用素 (universal quantifier), 存在作用素 (existential quantifier) であり, 全称作用素と存在作用素を併せて限定作用素 (quantifier) と呼ぶ. $\Leftrightarrow, \rightarrow, \wedge, \vee, \neg$ はそれぞれ等価 (equivalence), 含意 (implication), 論理積 (conjunction, and), 論理和 (disjunction, or), 否定 (negation, not) を表す論理演算子とする. 特に断りのない限り, $u, w, x, y, z$ で変数 (variable) 記号, $a, b$ で定数 (constant) 記号, $f$ で関数 (function) 記号, $p, q$ で述語 (predicate) 記号を表わす.

(1-1) 一階述語論理式の解釈 (interpretation) $I$ は $(D, C, F, P)$ の4項組で与えられる. ここで, $D$ は値集合, $C$ は各定数記号への $D$ の要素への割り当て, $F$ は各 $n$ 引数関数記号への $D^n \rightarrow D$ の要素の割り当て, $P$ は各 $n$ 引数述語記号への $D^n \rightarrow B$ の要素の割り当てである. ただし, 真 (true), 偽 (false) を表わす true, false の2値からなる集合を $B$ とする.

例えば, 一階述語論理式 $\forall x~p(f(b, x), a)$ に対して, 解釈 $I_0$ として

• $D$ を非負整数 (nonnegative integer) 全体からなる集合とし,
• $C$ として $a, b$ それぞれへ非負整数値 0, 1 を割り当て,
• $F$ として2引数関数記号 $f(u, w)$ へ非負整数上の加算 $u+w$ を割り当て,
• $P$ として2引数述語関数 $p(u, w)$ へ非負整数上の比較演算 $u>w$ を割り当てたとき (例えば $4>3$ の値は true である),

式 $\forall x~p(f(b, x), a)$ の解釈 $I_0$ のもとでの評価値は true となる.

以下の (1-1-1)～(1-1-3) の各論理式が, (a) 恒真 (valid), (b) 充足可能 (satisfiable) であるが恒真ではない, (c) 充足不能 (unsatisfiable) のいずれであるか判断し記号で答えよ. また, (b) である場合は, $D$ を非負整数 (nonnegative integer) 全体からなる集合として, 真にする解釈と偽にする解釈をそれぞれ一つずつ挙げよ. なお, 定数記号や関数記号が含まれないものは, それぞれ $C$ や $F$ は考えなくてよい.

(1-1-1) $(p(a) \wedge p(b)) \rightarrow \forall x~p(x)$
(1-1-2) $\forall x~(p(x) \vee q(x)) \rightarrow (\forall x~p(x) \vee \forall x~q(x))$
(1-1-3) $\neg \forall x~\neg p(x) \Leftrightarrow \exists x~p(x)$

(1-2) 以下で与えられる論理式 $E$ が恒真 (valid) であることを示すため, まず, $E$ の否定をスコーレム化 (Skolemization) し, 次いで, 導出原理 (resolution principle) を適用し, その式が充足不能であることを示す.

$A = \forall x~\forall y~(p(x, y) \rightarrow p(y, x))$
$B = \forall x~\forall y~\forall z~((p(x, y) \wedge p(y, z)) \rightarrow p(x, z))$
$C = \forall x~\exists y~p(x, y)$
$D = \forall z~p(z, z)$
$E = (A \wedge B \wedge C) \rightarrow D$

以下の (1-2-1)～(1-2-3) に答えよ. それぞれ導出過程も示すこと. なお, 解答には記号 $A, B, C, D$ を用いないこと.

(1-2-1) $\neg E$ の冠頭標準形 (prenex normal form) を示せ. 冠頭標準形は, すべての限定作用素が先頭にある閉論理式 (closed formula) である. ただし, 閉論理式は連言標準形 (和積標準形 : conjunctive normal form) で示すこと.

(1-2-2) (1-2-1) で得た論理式のスコーレム連言標準形 (Skolem conjunctive normal form) $\neg E'$ を求めよ.

(1-2-3) (1-2-2) で得た論理式 $\neg E'$ をもとに, 導出原理を用いて $\neg E'$ が充足不能であることを示せ.

(2) 有限集合 (finite set) $A$ について, $A$ の要素数を $|A|$ と書く. $A$ のべき集合 (power set) を $P(A)$ として, $P(A)$ 上の2項関係 (binary relation) $R_{P(A)}$ を

とする. 以下の各小問に答えよ.

(2-1) 任意の有限集合 $A$ について, $R_{P(A)}$ の以下の各性質が成立するかどうか答えよ. 証明は与えなくてもよい.

(2-1-1) 反射性 (reflexivity)
(2-1-2) 対称性 (symmetry)
(2-1-3) 反対称性 (antisymmetry)

(2-2) $|A| = 2$ の時, $|R_{P(A)}|$ を求めよ.
(2-3) $|A| = n$ の時, $|R_{P(A)}|$ を求めよ.
(2-4) $R_{P(A)}$ の反射的推移的閉包 (reflexive transitive closure) を $R_{P(A)}^{\ast}$ とする. $|A| = n$ の時, $|R_{P(A)}^{\ast}|$ を求めよ.

Kai#

Author#

KardeniaPoyu

Description#

(1) 決定性有限オートマトン (deterministic finite automaton) $M$ は 5 項組 $M = (Q, \Sigma, \delta, q_0, F)$ で与えられる. ここで, $Q, \Sigma, \delta, q_0, F$ は, それぞれ, 状態 (state) の有限集合, 入力記号 (input symbol) の有限集合 (アルファベット (alphabet)), 状態遷移関数 (state transition function), 初期状態 (initial state) ($q_0 \in Q$), 受理状態 (accepting state) の集合 ($F \subseteq Q$) である. また, $M$ が受理する言語 (認識する言語) を $L(M)$ と表す. 有限オートマトンに関する以下の各小問に答えよ.

(1-1) 決定性有限オートマトン $M = (Q, \Sigma, \delta, q_0, F)$ の状態 $p, q$ ($p \in Q, q \in Q$) が区別不能 (indistinguishable) とは, 任意の記号列 $w \in \Sigma^*$ に対し, $\hat{\delta}(p, w) \in F \iff \hat{\delta}(q, w) \in F$ が成り立つことであり, $p \simeq q$ と表す. ここで, $\Sigma^*$ は, $\Sigma$ 上の記号列すべての集合 (空系列を含む) を表す. また, 任意の状態 $r \in Q$ と任意の記号列 $x \in \Sigma^*$ に対し, $\hat{\delta}(r, x) \in Q$ を以下のように定義する.

• $x = \epsilon$ のとき, $\hat{\delta}(r, x) = r$ ($\epsilon$ は空系列を表す)
• $x = ya$ ($y \in \Sigma^*, a \in \Sigma$) のとき, $\hat{\delta}(r, x) = \delta(\hat{\delta}(r, y), a)$ 状態集合 $Q$ 上の 2 項関係 (binary relation) $\simeq$ が $Q$ 上の同値関係 (equivalence relation) であることを証明せよ.

(1-2) 決定性有限オートマトン $M_1 = (Q_1, \{0, 1\}, \delta_1, a, \{a, b\})$ が右の状態遷移表 (state transition table) で与えられたとき, 状態集合 $Q_1 = \{a, b, c, d, e, f, g, h, i\}$ が同値関係 $\simeq$ によって, どのような同値類 (equivalence class) に分割 (partition) されるか示せ.

(1-3) $L(M_1) = L(M)$ となる決定性有限オートマトン $M$ の中で, 状態数最小のものを $M_2$ とする. $M_2$ を状態遷移図 (state transition diagram) で示せ. 状態遷移図では, 初期状態, 受理状態それぞれが分かるように明示すること.

(1-4) $L(M_1) = L(M)$ となる決定性有限オートマトン $M$ の中で, (1-3) で示した $M_2$ の状態数が最小であることを証明せよ.

(2) 文脈自由言語 (context-free language) に対して次の反復補題 (Pumping Lemma) が知られている.

反復補題 (Pumping Lemma) 文脈自由言語 $L$ に対し, ある非負整数 $n$ が存在し, $L$ に属する $n$ 以上の長さの任意の文字列 $z$ に対して, ある部分文字列分解 $z = u v w x y$ が存在して, 以下が成り立つ. (i) $|v w x| \le n$ (ii) $v x \ne \epsilon$ ただし $\epsilon$ は空系列 (iii) $i \ge 0$ なる任意の $i$ に対して $u v^i w x^i y \in L$

以下の各小問に答えよ. 解答用紙には ⓐ～ⓠ とそれらに対応する解を列挙すること.

(2-1) 文脈自由言語 $L_A = \{a^m b^m \mid m \ge 5\}$ に対して反復補題が成り立つことを確かめたい. 以下の文章の空白を埋め, $L_A$ に対し反復補題が成り立つことを示せ. 空白 ⓐ～ⓘ にはそれぞれ, 指定された条件を満たす要素が入る. 例えば ⓐ 非負整数 に対応する要素は非負整数である 1, 40, 100 等である.

$n$ として ⓐ 非負整数 を選ぶ. $z = a^K b^K$ ただし, $K \ge n$ なる任意の文 $z$ に対して $z = u v w x y$ なる部分文字列分解として $u = a^{K-1}$, $v = \text{ⓒ 記号列}$, $w = \text{ⓓ 記号列}$, $x = \text{ⓔ 記号列}$, $y = \text{ⓕ 記号列}$ を選ぶ. 明らかに $|v w x| \le n$ であり, $v x \ne \epsilon$, および $i \ge 0$ なる任意の $i$ に対して $\text{ⓖ 記号列} \in L_A$ が成り立つ. なお $L_A$ を生成する文脈自由文法 (context-free grammar) は $(\{S_1, A_1\}, \{a, b\}, P_1, S_1)$ であり (表記の意味は下記参考を参照), ここで $P_1 = \{S_1 \rightarrow \text{ⓗ 記号列}, A_1 \rightarrow a b, \text{ⓘ 生成規則} \}$ である.

(2-2) 言語 $L_B = \{a^m b^m c^m \mid m \ge 0\}$ は文脈自由言語ではないことを反復補題を用いて証明したい. 以下の証明の空白を埋めよ. 空白 ⓙ～ⓠ にはそれぞれ, (2-1) と同様指定された条件を満たす要素が入る. ただし, ⓜ, ⓝ については終端記号の数量的性質に言及すること. また, ⓛ については使用した反復補題の条件を明示すること.

証明 背理法 (帰謬法; proof by contradiction) で証明する. 言語 $L_B$ が文脈自由文法であると仮定する. このとき仮定より $L_B$ に対して反復補題が成り立つ. 以下, 反復補題が成り立たないことを示し, 矛盾を導く. $n$ として $K$ という非負整数値を考える. 以降の議論は $K$ をパラメータとして考えているので, 任意の値 $K$ に与えても成立する. $L_B$ の定義より $K$ を超える長さの文 $z$ が存在する. 具体的に $z = a^K b^K c^K$ を考える. $z$ を $u v w x y$ に分割する際, すべての考え得る分割パターンに対して, 上記の矛盾を説明する必要がある.

場合 1: $v w x$ が終端記号 $c$ を含まない場合: このとき $y$ は ⓙ 記号列 を部分文字列として含む. また反復補題の条件 (ii) が成り立つとすると, $v, x$ について以下が成り立つ. ⓚ $v, x$ に関する条件 したがって $i = 0$ とおいて $L_B$ に含まれるはずの文 $u w y$ を考えたとき, $u w y$ は $L_B$ に属さない. なぜならば ⓛ 証明 すなわち反復補題の条件 (iii) を満たすことはできず, 反復補題を満たさない.

場合 2: $v w x$ が ⓜ 終端記号に関する条件 場合: 対象の対称性 (symmetry) より場合 1 と同様である.

場合 3: その他の場合, すなわち $v w x$ が ⓝ 終端記号に関する条件 場合: 場合 3 はそもそも起こりえない. なぜならば ⓞ 証明

いずれの場合であっても反復補題を満たさず, よって, 矛盾を生じる. 以上の議論は仮定していた命題「言語 $L_B$ は文脈自由文法である」が偽であることを示している. Q.E.D.

参考 文脈自由文法 (context-free grammar) $G$ は 4 項組 $G = (N, T, P, S)$ で与えられる. ここで $N, T, P, S$ は, それぞれ, 非終端記号 (non-terminal symbol) 集合, 終端記号 (terminal symbol) 集合, 生成規則 (production rule) 集合, 開始記号 (start symbol) である.

Kai#