使用泵引理证明先增后减二进制序列语言L是否为上下文无关语言

你之前初步判断L是上下文无关语言的结论有误，我们可以用上下文无关语言的泵引理完成反证，具体步骤如下：

前置知识：上下文无关泵引理 #

对任意上下文无关语言A，存在正整数泵长度p，使得任意长度≥p的字符串s∈A，都可以拆分为s = uvxyz，且满足三个约束：

• 对任意非负整数i，uvⁱxyⁱz ∈ A
• |vy| > 0（v和y不能同时为空）
• |vxy| ≤ p（v、x、y三个子串的总长度不超过p）

构造反例字符串 #

设p为L的泵长度，我们构造符合L要求的字符串s：

1. 所有参与构造的数字均为p位二进制正整数，无前置零，数值范围为[2^{p-1}, 2^p - 1]，保证每个数字长度相同，大小直接和二进制数值正相关。
2. 令a_k = 2^{p-1} + 2^{k-1} - 1，即：
   • a₁为100...0（p位，数值2^{p-1}）
   • a₂为100...01（p位，数值2^{p-1}+1）
   • ...
   • a_p为1011...1（p位，数值2^p - 2）
3. 最终构造的s为：s = a₁#a₂#...#a_p#a_p#a_{p-1}#...#a₂#a₁
   显然s是严格递增到峰值a_p、再严格递减的先升后降序列，属于L，且总长度远大于p，符合泵引理的长度要求。

分情况讨论导出矛盾 #

由于|vxy| ≤ p，而单个数字长度为p，两个数字加中间分隔符#的总长度为2p+1>p，因此vxy最多只能覆盖单个数字的全部、或单个数字的部分加相邻#和另一个数字的部分，不可能覆盖两个完整数字，我们分三种情况讨论：

• 情况1：vxy完全落在峰值左侧的递增段
  取i=0得到uxz，相当于删除v和y对应的字符：
  • 如果v或y包含某个数字的开头1，删除后剩余的数字部分会以0开头，出现前置零，不符合L的正整数二进制编码要求，不属于L。
  • 如果v或y是数字的中间/末尾字符，删除后该数字长度变为p-t（t≥1），数值≤2^{p-t}-1 ≤2^{p-1}-1 <2^{p-1} ≤左侧相邻数字的数值，导致递增段出现下降，不符合先升后降要求，不属于L。
• 情况2：vxy完全落在峰值右侧的递减段
  和情况1对称，取i=0删除v和y后，要么出现前置零，要么某个数字变短后数值大于右侧相邻数字，导致递减段出现上升，不符合要求，不属于L。
• 情况3：vxy覆盖峰值的部分内容
  取i=0删除v和y后，被修改的峰值数字长度变为p-t（t≥1），数值≤2^{p-t}-1 ≤2^{p-1}-1 <2^{p-1} ≤其左侧相邻的a_{p-1}的数值，导致峰值左侧的递增段出现下降，不符合先升后降要求，不属于L。

所有可能的拆分情况都违反泵引理的约束，因此L是上下文无关语言的假设不成立，L不属于上下文无关语言。

内容的提问来源于stack exchange，提问作者Chaot1c