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

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.

State Pumping Lemma for Regular Languges

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

Recursive languages are a subset of:a.Recursively enumerable languagesb.Context-sensitive languagesc.Context-free languagesd.Regular languages

The equivalence between Linear Bounded Automata (LBA) and Context-Sensitive Languages is established by:a.Sipser's Theoremb.LBA-CSL Equivalencec.CSL-LBA Equivalenced.Pumping Lemma for CSL