Pumping Lemma Proving L_1 & L_2 Not Regular

  • Thread starter needhelp83
  • Start date
In summary, we can use the pumping lemma to prove that the language L_1 is not regular by choosing the string s = a^pba^{p+1}. When we pump y to i=2, we end up with a string that does not follow the rules of the language, contradicting the pumping lemma. This shows that L_1 is not a regular language.
  • #1
needhelp83
199
0
Problem:

Consider the languages over the alphabet [tex]\sum = {a,b}[/tex] defined by [tex] L_1 = {a^{k}w|k [/tex] is the number of consecutive a's at start, w is the rest of the string, and the number of a's in w is greater than or equal to k},

and

[tex] L_2 = {a^{k}w|k [/tex] is the number of consecutive a's at start, w is the rest of the string, and the number of a's in w is less than or equal to k},

For language, use pumping lemma to prove that the language is not regular. For each proof, you must state s in terms of the integer p from the pumping lemma, and then explain clearly why some [tex]xy^{i}z[/tex] is not in the language specific for i.

ATTEMPTED SOLUTION:
Assume [tex]L_1[/tex] is a regular language. If [tex] s=a^pba^p [/tex] and [tex]x=a^p, y=ba^p, and z=\epsilon [/tex]. Using the pumping down method, pump y to i=0. This gives [tex] a^p[/tex] which returns a greater amount of a's in x. This is a contradiction, thus [tex] L_1 [/tex] is not a regular language.

I don't believe this is right. I am really struggling with this pumping and looking for any help I can get. Thanks!
 
Physics news on Phys.org
  • #2




Hi there, thank you for sharing your attempted solution. I believe there are a few issues with your proof. First, you have not clearly stated what p represents and how you are using it in your proof. Second, when you pump y to i=0, you should end up with a string that has a different number of a's at the start than the original string s. However, this does not necessarily mean that it is not in the language L_1. In fact, if you pump y to i=0, you will end up with the string a^pba^{p-1}, which is still in the language L_1.

To prove that L_1 is not a regular language, we can use the pumping lemma by choosing the string s = a^pba^{p+1} (note that p is the integer from the pumping lemma). According to the pumping lemma, s can be divided into three parts: xyz, where |xy| <= p, |y| > 0, and xy^iz is also in the language for any integer i >= 0.

Now, let's consider the string xy^2z. Since |xy| <= p, y must consist of only a's. Therefore, when we pump y to i=2, we will have more a's at the start than the original string s. However, the rest of the string, w, will still have the same number of a's as the original string, which is p+1. This means that xy^2z is not in the language L_1, as it does not follow the rule that the number of a's in w must be greater than or equal to the number of consecutive a's at the start. This contradicts the pumping lemma, and therefore L_1 is not a regular language.

I hope this explanation helps. Keep in mind that when using the pumping lemma, it's important to choose the right string and clearly state how you are using the integer p. Also, make sure to carefully consider how pumping affects the number of a's at the start and in the rest of the string. Good luck!
 
  • #3




Your attempted solution is on the right track, but there are a few errors. Let's break down the pumping lemma and apply it to L_1.

The pumping lemma states that for any regular language L, there exists a constant p (the "pumping length") such that any string s in L with length greater than or equal to p can be split into three parts, s=xyz, where x and y are substrings of s and z is the remaining suffix of s. Furthermore, the following conditions must hold:

1. |xy| ≤ p (the length of x and y combined is less than or equal to p)
2. |y| > 0 (y is not an empty string)
3. For all i ≥ 0, xy^iz ∈ L (pumping y any number of times results in a string that is still in L)

Now, let's apply this to L_1. Assume L_1 is a regular language. This means that there exists a pumping length p such that for any string s in L_1 with length greater than or equal to p, the conditions of the pumping lemma hold.

Let's choose s = a^pba^p. This string has length 2p+1, which is greater than or equal to p. So, we can apply the pumping lemma to s.

According to the pumping lemma, we can split s into three parts, s=xyz, where |xy| ≤ p and |y| > 0. Let's choose x = a^p and y = b. This means that z = a^p, since s = a^pba^p. This satisfies the first two conditions of the pumping lemma.

Now, let's consider the third condition. For any i ≥ 0, xy^iz must be in L_1. However, when we pump y to i = 0, we get xy^0z = xz = a^pa^p = a^(2p), which is not in L_1. This is a contradiction to the third condition of the pumping lemma, which means that our initial assumption that L_1 is a regular language must be false.

We can use a similar approach to prove that L_2 is not a regular language. I'll leave that as an exercise for you to try.

Remember, the key to using the pumping lemma is to choose a string s that is in the
 

1. What is the Pumping Lemma and how does it relate to proving that languages L1 and L2 are not regular?

The Pumping Lemma is a tool used in theoretical computer science to prove that a language is not regular. It states that for any regular language, there exists a "pumping length" where any string longer than that length can be divided into smaller parts that can be repeated an infinite number of times while still remaining in the language. If a language does not meet this condition, it is not regular. By using this lemma, we can show that languages L1 and L2 cannot be regular.

2. How do you apply the Pumping Lemma to prove that L1 and L2 are not regular?

To prove that L1 and L2 are not regular, we first assume that they are regular and then use the Pumping Lemma to reach a contradiction. We choose a pumping length and a string longer than that length from either L1 or L2. We then divide the string into smaller parts and show that no matter how many times we repeat those parts, the resulting string is not in the language. This proves that the language is not regular, contradicting our initial assumption.

3. Are there any limitations to the Pumping Lemma in proving the non-regularity of L1 and L2?

Yes, the Pumping Lemma can only be used to prove that a language is not regular, but it cannot prove that a language is regular. Additionally, there may be languages that do not meet the conditions of the lemma but are still regular. Therefore, the Pumping Lemma should be used in conjunction with other techniques to prove the non-regularity of a language.

4. Can the Pumping Lemma be used to prove the regularity of languages L1 and L2?

No, the Pumping Lemma can only be used to prove that a language is not regular. It cannot be used to prove the regularity of a language.

5. Why is it important to prove the non-regularity of languages L1 and L2?

Proving the non-regularity of languages L1 and L2 is important because it helps us understand the limitations of regular languages and the types of languages that cannot be recognized by finite automata. It also allows us to identify and classify different types of languages, which can have practical applications in fields such as natural language processing and compiler design.

Similar threads

  • Engineering and Comp Sci Homework Help
Replies
1
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
1K
  • Electromagnetism
Replies
16
Views
988
  • Engineering and Comp Sci Homework Help
Replies
1
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
6
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
988
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
8
Views
1K
Back
Top