计算理论-在上下文无关的语言中使用抽水引理 [英] Theory of computation - Using the pumping lemma for context free languages
问题描述
我正在复习计算理论课程的笔记，但在理解如何完成特定证明方面遇到困难。问题是：
I'm reviewing my notes for my course on theory of computation and I'm having trouble understanding how to complete a certain proof. Here is the question:
A = {0^n 1^m 0^n | n>=1, m>=1} Prove that A is not regular.
很明显，必须使用抽水引理。因此，我们有
It's pretty obvious that the pumping lemma has to be used for this. So, we have
- | vy | > = 1
- | vxy | < = p（p是抽水
的长度，> = 1） - uv ^ ixy ^ iz对于所有i> = 0的li存在$ b
- |vy| >= 1
- |vxy| <= p (p being the pumping length, >= 1)
- uv^ixy^iz exists in A for all i >= 0
试图考虑要选择的正确字符串似乎有点之以鼻。我当时在想0 ^ p 1 ^ q 0 ^ p，但是我不知道我能否默默地制作aq，并且由于u上没有界线，所以这会使事情变得不规则。
Trying to think of the correct string to choose seems a bit iffy for this. I was thinking 0^p 1^q 0^p, but I don't know if I can obscurely make a q, and since there is no bound on u, this could make things unruly..
那么，如何解决呢？
推荐答案
如果使用，它将变得更加简单泵引理的定义适用于常规语言，而不适用于CFG。任何常规字符串s = xyz都必须满足的三个条件是：
It'll be much simpler if you use the definition of the pumping lemma applying to regular languages, not the one applying to CFGs. The three conditions that any regular string s = xyz must have are:
- 对于每个i> = 0，xy ^ iz在A
- | y | > = 0
- | xy | < = p
尝试使用这三个条件再次使用0 ^ p1 ^ q0 ^ p。
Try using 0^p1^q0^p again using these three conditions.
提示：因为我们有0 ^ p，所以y仅包含0。因此，当我们输入更多y（考虑xyyz）时，将不会获得该语言的字符串。
Hint: Because we have 0^p, y will only consist of 0's. Therefore, when we "pump in" more y's (consider xyyz), we will not get a string in the language.
这篇关于计算理论-在上下文无关的语言中使用抽水引理的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
