Question

Let L = {0 r | r = s 2 , s a positive integer}. Give the simplest proof you can that L is not regular using the pumping lemma.

Answer 1

First see what is pumping lemma:

pumping lemma is used for proof of irregularity of language.Thus, if language is regular then it always satisfies pumping lemma.

If there exist at least one string made from pumping which is not in L(Language) then we can say that L is surely not a regular language.but the vice vers is not true always, example > if pumping lemma true , does not mean language is regular.

we have given L : {0 r|r = s2, s a positive integer}

for giving proof for L in not regular we can use proof by contradiction, Here are steps:

>suppose L is regular

>since L is regular we can apply pumping lemma and assert existence of number n > 0 it can satisfy the property.

>give particular number such that

s belongs to positive integer

>by pumping lemma , there are string u, v, w.pick particular number s in N and argue that uv does not belong to L

so we can defined that language is not regular by pumping lemma.