Knowee
Questions
Features
Study Tools

Part OneApplying this new pumping lemma can require the same sort of creative decisions as the one for regular languages. Previously we showed this language was not regular:L={apโˆˆ{a}โˆ—|pย is a prime numberย }๐ฟ={๐‘Ž๐‘โˆˆ{๐‘Ž}โˆ—|๐‘ย is a prime numberย }Can you prove that it is not context-free?Here is the start of the proof.Assume L๐ฟ is context-free, then the context-free pumping lemma applies, with a pumping length n๐‘›.Then consider ap๐‘Ž๐‘ where pโ‰ฅn๐‘โ‰ฅ๐‘› is a prime number.Then by the lemma, ap=uvxyz๐‘Ž๐‘=๐‘ข๐‘ฃ๐‘ฅ๐‘ฆ๐‘ง with the usual conditions.Let s=|uxz|๐‘ =|๐‘ข๐‘ฅ๐‘ง|, and r=|vy|๐‘Ÿ=|๐‘ฃ๐‘ฆ|. Notice that p=s+r๐‘=๐‘ +๐‘Ÿ.Then |uvixyiz|=s+ir|๐‘ข๐‘ฃ๐‘–๐‘ฅ๐‘ฆ๐‘–๐‘ง|=๐‘ +๐‘–๐‘Ÿ, and by the context-free pumping lemma, as+irโˆˆL๐‘Ž๐‘ +๐‘–๐‘Ÿโˆˆ๐ฟ, i.e. s+ir๐‘ +๐‘–๐‘Ÿ is prime.Now see if you can pick a value for i๐‘– that leads to a contradiction. You might want to use the proof of non-regularity for inspiration.

Question

Part OneApplying this new pumping lemma can require the same sort of creative decisions as the one for regular languages. Previously we showed this language was not regular:L={apโˆˆ{a}โˆ—|pย is a prime numberย }๐ฟ={๐‘Ž๐‘โˆˆ{๐‘Ž}โˆ—|๐‘ย is a prime numberย }Can you prove that it is not context-free?Here is the start of the proof.Assume L๐ฟ is context-free, then the context-free pumping lemma applies, with a pumping length n๐‘›.Then consider ap๐‘Ž๐‘ where pโ‰ฅn๐‘โ‰ฅ๐‘› is a prime number.Then by the lemma, ap=uvxyz๐‘Ž๐‘=๐‘ข๐‘ฃ๐‘ฅ๐‘ฆ๐‘ง with the usual conditions.Let s=|uxz|๐‘ =|๐‘ข๐‘ฅ๐‘ง|, and r=|vy|๐‘Ÿ=|๐‘ฃ๐‘ฆ|. Notice that p=s+r๐‘=๐‘ +๐‘Ÿ.Then |uvixyiz|=s+ir|๐‘ข๐‘ฃ๐‘–๐‘ฅ๐‘ฆ๐‘–๐‘ง|=๐‘ +๐‘–๐‘Ÿ, and by the context-free pumping lemma, as+irโˆˆL๐‘Ž๐‘ +๐‘–๐‘Ÿโˆˆ๐ฟ, i.e. s+ir๐‘ +๐‘–๐‘Ÿ is prime.Now see if you can pick a value for i๐‘– that leads to a contradiction. You might want to use the proof of non-regularity for inspiration.

...expand
๐Ÿง Not the exact question you are looking for?Go ask a question

Solution

Sure, let's continue the proof.

We know that s + ir is prime for all i โ‰ฅ 0. Let's choose i = 2. Then we have s + 2r. But we know that s and r are both greater than or equal to 1 (since they are lengths of strings), so s + 2r is at least s + r + 1 = p + 1, which is greater than p.

But p was chosen to be a prime number, and p + 1 is not prime (since it's one more than a prime number). So we have a contradiction: the pumping lemma says that as + 2r should be in L (since it's of the form s + ir), but as + 2r = ap + 1, and p + 1 is not prime, so ap + 1 is not in L.

Therefore, our assumption that L is context-free must be false. So L is not a context-free language.

This problem has been solved

Similar Questions

What is the pumping lemma used for in formal language theory?1 pointTo prove that a language is regularTo prove that a language is not context-freeTo prove that a language is context-sensitiveTo prove that a language is recursively enumerable

State Pumping Lemma for Regular Languges

Which of the following is a regular language? ans. String with even number of Zeroโ€™s Palindrome string String with substring wwr in between String whose length is a sequence of prime numbers

In the application of the Pumping Lemma for a language, the string w belonging to L is divided into _____ parts.a)6b)3c)5d)2

Which of the following is a regular language?ย ans.String whose length is a sequence of prime numbersString with even number of Zeroโ€™sPalindrome stringString with substring wwr in between Previous Marked for Review Next

1/1

Upgrade your grade with Knowee

Get personalized homework help. Review tough concepts in more detail, or go deeper into your topic by exploring other relevant questions.