# Pumping Lemma proof for L=0^p 1^p 0^p 1^p-: Review my proof please-:

• MHB
• shivajikobardan
In summary, the speaker is requesting a review of their proof and asking for clarification on certain points. They point out that case 1) where $v=0^p$, $x=1^p$, and $y=\varepsilon$ is prohibited by condition (2) of the lemma. They also mention that case 3) is true because $L$ contains words that do not follow the form $0^p1^p0^p1^p$ or even $0^n1^n0^n1^n$ for any $n$. The speaker requests more explanation for case 3) and notes that it assumes $y=\varepsilon$. They also mention that case 5) is not clear and
shivajikobardan
Please review my proof. Is this correct or not?

Why do you consider case 1) where $v=0^p$, $x=1^p$ and $y=\varepsilon$? It is prohibited by condition (2) of the lemma.

In case 3) you write: "$L$ contains pattern not in form $0^p1^p0^p1^p$". This is true: $L$ contains words that do not have this form and do not even have the form $0^n1^n0^n1^n$ for any $n$. What conclusion do you draw from this? Then you write: "So $\notin L$. What exactly does not belong to $L$? It's a bad style to write such ambiguous claims in a proof. Finally, case 3) assumes that $y=\varepsilon$. What if this is not so?

The description of case 5) is not clear (does $y$ have to be empty? does $x$ has to end on the boundary between zeros and ones?), but it seems that it is again prohibited by condition 2 of the lemma.

A proof should contain more words. For example, this proof should start like this: "Let $p$ be the number whose existence is stated in the lemma. Let $w=0^p1^p0^p1^p$. Consider the following five exhaustive cases".

Please type you proof in the body of the forum post. Pictures can easily be described, for example: "$vxy$ spans the first boundary between 0s and 1s" (the diagram at the bottom of page 1). The bottom of page 1 is far too dark for comfortable reading.

## 1. What is the Pumping Lemma proof for L=0^p 1^p 0^p 1^p?

The Pumping Lemma is a theorem in formal language theory that helps to prove whether a given language is regular or not. It states that if a language L is regular, then there exists a constant number p (known as the "pumping length") where any string longer than p can be divided into three parts: uvw, such that v is non-empty, uvw is in L, and for any natural number n, uv^nw is also in L. In the case of L=0^p 1^p 0^p 1^p, this means that if the language is regular, there should exist a pumping length p where any string consisting of p 0's followed by p 1's followed by p 0's followed by p 1's can be pumped in the manner described above.

## 2. How do you prove that L=0^p 1^p 0^p 1^p is not regular using the Pumping Lemma?

To prove that L is not regular, we must show that for any pumping length p, there exists a string in L that cannot be pumped. This can be done by assuming that L is regular and then using the Pumping Lemma to choose a string that cannot be pumped, leading to a contradiction. In the case of L=0^p 1^p 0^p 1^p, we can choose the string s=0^p 1^p 0^p 1^p and show that no matter how we divide it into uvw, we can always pump v or w in such a way that the number of 0's and 1's in the resulting string will not be equal, thus not satisfying the conditions of the language.

## 3. Can you provide an example of a string in L=0^p 1^p 0^p 1^p that cannot be pumped?

An example of a string that cannot be pumped in L=0^p 1^p 0^p 1^p is s=0000111100001111, where p=4. If we divide this string into uvw such that |v|=4, then v must contain at least one 0 and one 1, and thus pumping v would result in a string with an unequal number of 0's and 1's. Similarly, if we choose |v|=5, pumping w would result in an unequal number of 1's and 0's. Thus, this string cannot be pumped in a way that satisfies the conditions of the language.

## 4. Is the Pumping Lemma proof for L=0^p 1^p 0^p 1^p a sufficient condition for proving that a language is not regular?

No, the Pumping Lemma is not a sufficient condition for proving that a language is not regular. It only provides a necessary condition, meaning that if the conditions of the lemma are not satisfied, then the language is not regular. However, there are languages that do satisfy the conditions of the lemma but are not regular. Therefore, the Pumping Lemma should be used in conjunction with other methods and proofs to determine the regularity of a language.

## 5. Can the Pumping Lemma be used to prove that a language is regular?

Yes, the Pumping Lemma can be used to prove that a language is regular, but it is not the only method. It can be used to show that a language is not regular, but it cannot be used to prove that a language is regular. To prove that a language is regular, other methods such as constructing a regular expression or a finite automaton may be used.

• Programming and Computer Science
Replies
2
Views
1K
• Calculus and Beyond Homework Help
Replies
24
Views
2K
• Precalculus Mathematics Homework Help
Replies
30
Views
3K
• Calculus and Beyond Homework Help
Replies
6
Views
2K
• Calculus and Beyond Homework Help
Replies
4
Views
1K
• Calculus and Beyond Homework Help
Replies
5
Views
1K
• Calculus and Beyond Homework Help
Replies
3
Views
874
• Topology and Analysis
Replies
2
Views
2K
• Precalculus Mathematics Homework Help
Replies
1
Views
876
• Topology and Analysis
Replies
1
Views
1K