0

抽引引理定义(来自 wiki)

令 L 为常规语言。那么存在一个整数 p ≥ 1 仅取决于 L 使得 L 中的每个长度至少为 p 的字符串 w(p 称为“泵送长度”[4])可以写成 w = xyz(即 w 可以是分为三个子串),满足以下条件:

|是| ≥1;|xy| ≤ p 对于所有 i ≥ 0,xyiz ∈ L

假设我要测试正则表达式 011 因为它是正则表达式m,所以存在至少长度为 p 的字符串 w 满足 w=xyz

这个自动机的数量是 3,p 应该 >= 3 但只有接受这个自动机的字符串是 011 所以我选择 011 因为 w 我可以分解 3 部分 011 = xyz 但我怎么能打破?我不能满足|y| ≥1;|xy| ≤ p 对于所有 i ≥ 0,xyiz ∈ L

由于它只接受 011 我该如何抽水?我哪里错了

4

2 回答 2

2

p为 4。那么在L中没有长度至少为p的字符串w,因此任何形式为“ L中长度至少为p […]的每个字符串w ”的陈述都是空洞的。所以抽水引理是满足的。

于 2015-04-17T01:13:24.927 回答
-2

抽引引理通常适用于无限正则语言。And 不用于证明 L 是正则 它用于证明 L 不是正则 但它满足所有无限正则语言

于 2019-07-31T02:25:00.643 回答