常规语言的最小泵送长度

Question

考虑语言

L = { a3n + 5 | n ≥ 0 }

L的最小抽吸长度是多少？

Answer 1

通过常规语言L的最小泵送长度，我理解最小p，这样长度至少为u ∈ L的每个字符串p都可以写为u = xyz，其中|xy| ≤ p，y ≠ λ所有xyiz ∈ L的i ≥ 0。在您的情况下，可以用a3n + 5 ∈ L编写每个字符串n > 0：

a3n + 5 = a5(a3)ia3

其中i ≥ 0。该分解满足上述条件，因此L的最小泵浦长度为8。请注意，n ≥ 0不起作用，因为无法泵送字符串a5。还请注意，L的最小DFA具有8状态，尽管通常常规语言的最小抽运长度可以小于其最小DFA中的状态数。