设 A 是 {1,2,3} 上的语言。使用 A 和字符串变量 p 和 q，我们在数学上定义语言 B {0,1,2,3}：
B = { p0q1 | p为空或者是A中的字符串，y由一个或多个2}
组成对于下面的每个场景，说出 B 所属的最小语言类。 a) 存在一个识别 A 的（终止）算法。 b) A 是上下文无关语言。
我的推理如下，但我不确定我是否正确：
A 可以被最终终止的算法识别。如果 A 存在这样的算法，那么 B 也可以被图灵机识别。该机器将字符串 w 作为输入并生成 p0q1 形式的所有可能字符串，其中 p 是 A 中的字符串，q 由一个或多个 2 组成。如果 w 在 B 中，图灵机最终会产生 w。因此，B 是一种递归可枚举语言。
但是，如果A是上下文无关语言，并不一定意味着B也是上下文无关的。为了证明 B 是上下文无关的，我们必须证明生成 B 的上下文无关文法的存在。但是，我们可以使用泵引理来证明 B 不是上下文无关的。例如，考虑字符串 z = 12^n03^n，其中 n 是泵浦长度。由于 z 在 B 中，它可以写成 p0q1，其中 p 为空或 A 中的字符串，q 是一个或多个 2 的序列。如果我们通过重复两次或更多次来抽取 q，我们将得到一个不在 B 中的字符串，因为 1 和 3 的数量将不同。因此，B 不是上下文无关语言。