0

以下语言的最小抽水长度是多少 L=10 (11* 0)* 0

我读过这样的声明

s = xyz = 10100 其中 x=10,y=10 和 z=0 使得 xyiz∈L (即 10(1∊0)*0 ) 看起来最小泵送长度为 5 ,但事实并非如此,我们可以随时重复 y(或者应该重复)并且 y≠≠ ∊ 这意味着我们不能使用来自 L 的 3 个或更少长度的字符串进行泵送,因此 y 可以是 10(最小值),因此我们用于泵送的最小字符串 S 是 10100 的长度5,但是无法从给定的语言生成长度为 4 的字符串(这不是我们的错)。所以我们可以说我们使用 4 个或更多长度的字符串 s 来抽吸属于 L 的。因此抽吸长度是 4

但是,我对此感到困惑。y = 10,那么是什么让作者说三个或更少的抽水长度可能?它必须是两个或更少。不是吗?如果泵送长度为 4 是可能的,它必须被 Language L 接受。不是吗?请帮我找到这个问题的最小 puping 长度

4

1 回答 1

0

最小抽吸长度是一个最小常数C,这样任何长度大于或等于的语言字符串C都可以被抽吸(据我所知)。引文的作者说,对于正则表达式,可以抽取的现有字符串的最小长度为 5,但该语言中没有长度为 4 的字符串,因此可以肯定地说最小抽取长度为 4,因为它适用于定义。

于 2016-01-29T15:27:20.147 回答