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.
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.
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
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.