求助：语言L对应的有限自动机规模与状态数的相关证明

我来帮你一步步拆解这两个证明点，先从构造O(n)规模的非歧义有限自动机开始，再证明确定无εFA的状态下界。

一、构造O(n)规模的非歧义有限自动机接受L #

首先明确语言定义：$L = {0,1}^*1{0,1}n$，即所有包含一个1且该1后面恰好跟$n$个任意字符的字符串（字符串总长度至少为$n+1$）。

我们可以构造这样一个非歧义NFA：

• 状态集合：$Q = {q_0, q_1, ..., q_n}$，共$n+1$个状态（显然是$O(n)$规模）
• 起始状态：$q_0$
• 接受状态：$q_n$
• 转移规则：
  • 从$q_0$出发，输入0或1都可以回到$q_0$（处理任意前缀）；输入1还可以转移到$q_1$（标记我们找到了那个关键的1）
  • 对于$1 ≤ k ≤ n-1$，从$q_k$出发，输入0或1都转移到$q_{k+1}$（依次处理关键1后面的$n$个字符）
  • $q_n$是接受状态，无需出转移（或添加自环不影响接受性）

非歧义性证明 #

对于任何属于$L$的字符串$s$，只有唯一一条路径能到达接受状态$q_n$：

• 路径前半部分一直在$q_0$循环，直到遇到$s$中那个“后面跟$n$个字符的1”，此时转移到$q_1$
• 之后每一步依次转移到$q_2,...,q_n$，恰好对应这个1后面的$n$个字符
• 不存在其他路径能到达$q_n$：要么提前进入$q_1$但后续字符不足$n$个，要么错过关键1无法进入$q_1$序列。因此这个NFA是非歧义的，且规模为$O(n)$。

二、证明任何接受L的无ε确定FA至少有$2^n$个状态 #

这里用Myhill-Nerode定理最直接：确定有限自动机的最小状态数等于语言的等价类数量（两个字符串等价当且仅当对任意后缀$z$，$xz∈L$和$yz∈L$同时成立或不成立）。我们只需要找到$2^n$个两两不等价的字符串即可。

构造两两不等价的字符串 #

考虑所有长度为$n$的二进制字符串集合$S = {0,1}^{n$，共有$2}n$个元素。对于任意两个不同的字符串$x,y∈S$，存在某个位置$i$（$0≤i<n$）使得$x[i]≠y[i]$（比如$x[i]=1$，$y[i]=0$）。

现在构造后缀$z$：取$z$为长度$i+1$的任意字符串（比如全0）。此时：

• $xz$的总长度为$n + (i+1) = n+i+1$，其倒数第$n+1$位的索引为$(n+i+1-1) -n = i$，也就是$x[i]$
• 根据$L$的定义，$xz∈L$当且仅当$xz$的倒数第$n+1$位是1，即$x[i]=1$
• 同理，$yz∈L$当且仅当$y[i]=1$

因为$x[i]≠y[i]$，所以$xz∈L$和$yz∈L$恰好一个成立，说明$x$和$y$属于不同的等价类。

结论 #

由于$S$中有$2^{n$个两两不等价的字符串，根据Myhill-Nerode定理，接受$L$的最小确定FA至少需要$2}n$个状态。而无ε确定FA的状态数不会小于最小确定FA的状态数，因此任何接受$L$的无ε确定FA都至少拥有$2^n$个状态。

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