问题标签 [pumping-lemma]

这是我尝试过的简单有限自动机，我做错了什么？

您好我想知道是否有一个正则表达式可以执行以下操作：

从一个字符串中选择所有子字符串：

• 从&和开始
• 在( n >= 0)之后有n个字符&

并且那些子字符串不是

• &
• '
• <
• >或者
• "

例如，给定字符串

是否有一个只返回子字符串的正则表达式 &partners？

我的直觉说不，因为我需要一个上下文无关的语法，但我怎样才能证明呢？是否有正则表达式可以用泵引理对其进行测试？

或者一个正则表达式实际上存在而我的直觉是错误的？

谢谢

以下语言的最小抽水长度是多少 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 长度

语言：

我们拿话

这显然属于语言，因为 j = k = l

w = uvxyz

1. |vxy| <= n

2. |维| > 1

现在 v 和 y 可以是：

1. 只是一个字符，如果我们抽出单个字符，这个词就不再是语言

2. 两个字符，第三个字符的数量会更少，所以这个词不在语言中

所以，这种语言不是 CF 的证明不应该用标准的泵引理来做，只是用 ogdens 引理，但我不明白为什么上面的证明是无效的。

我有一个使用抽水引理来证明语言是否是上下文无关的测试。我正在尝试解决一些练习问题，但事情并没有那么好......

练习题是：对于a)到j)，证明下面的语言是否是上下文无关的。如果它是上下文无关的，请给出生成它的上下文无关文法。

前两个是：

如果有人可以解决前两个问题，并详细解释他们是如何做到的，我相信我可以自己解决剩下的问题（c 到 j）。

我无法证明特定语言是非常规的。语言定义为

L _a = { wz : w,z ∈ {0,1}* 和 |w| > |z|}

我不知道如何接近这个。无论我选择什么字符串，我总是遇到 w 和 z 对我来说是移动目标的问题；我无法创建无法抽出或以其他方式矛盾的字符串。关于这个正确方向的任何想法？

如果我让 stringw成为a^mb^m，那么我们知道这y将仅由a's 组成，因为规则|xy| <= m。

如果我设置i=0，那么左侧的 'sww^R会a比右侧的少。因此，它证明了这种语言是不规则的。

但是，我的教科书（林茨的《形式语言和自动机简介》第 118 页）说，如果我选择w = a^2m并让y = aa，那么我会失败。

但怎么会呢？

在我看来，无论x, y,z是什么，第一个会比第二个a^2m拥有更少a或更多的 's 。ia^2m

这很奇怪，但通过抽引理，说

让我们L成为一种常规语言。存在一个常数n，使得对于这样的每个字符串，w我们都可以闯入也在 中的这样。L|w| >= nwxyzxy*zL

这个引理很强大，因为它适用于所有常规语言。但是如果是常规语言L = a呢？里面只有一个字（a）。在这种情况下，抽水引理如何工作？

我试图使用抽水引理证明以下语言不规则。

L = {a ^k b ^3l a ^l | k ≥ 1 , l ≥ 0}

我决定选择 w = ab ^3p a ^p，然后选择 |w| = 4p+1 ≥ p

有小费吗？

谢谢！

L = {a^nbc^n| i 大于 1 且小于 100 ，n 大于 1}

我想我误解了cfl 的抽引引理。为什么我不能选择一个单词 z = a^ncb^n 然后将其拆分为 u= a^sv = a^ns w=epsilon x=b ,y= b^n 然后用 i=0 泵送它然后得到一个矛盾因为 0 b 不满足语言？我可能在这里遗漏了一些东西。