Pumping lemma on regular languages

Question

I'm fairly new to Formal Languages and I am still learning the pumping lemma.

Is it possible to know if a language is regular without knowing it's grammar?

Consider the language L over alphabet Σ={3,5} of all words for which the arithmetic sum of the constituent symbols is divisible by 5.

Now I don't know if this language is regular or not.

I assumed it to be not regular and tried to prove that it is not regular using Pumping lemma for regular languages.

I took n=6 and 'w' as 335333 here 3+3+5+3+3+3=20 which is divisible by 5, so this word belongs to L.

Sub-strings : x=33, y=53, z=33 So conditions |y|>=1 is true and |xy|<=n i.e. 6 is also true.

(w)^i=x(y)^iz

w^i=33(53)^i33

now for i=2 we get string as 33535333 where sum is 3+3+5+3+5+3+3+3=28, not divisble by 5. Hence, this language is not a regular language.

But then after some thought I was able to make a DFA, which means that this Language L should be regular.By making a pentagon with edges having 3 and self loops of 5 on each corner.(Can't post the image). Start state as it's final state.

Now I don't know what's wrong in my Pumping lemma proof.

I'd appreciate any hints or comments that may help me.

Many thanks in advance.

Answer 1

Your pumping lemma proof goes wrong right away; you say “I took $n=6$”. But you don't get to pick $n$. The pumping lemma only tells you that if $L$ is irregular then there exists some such $n$, not what it will be.

And then you make a similar mistake later, when you pick $u,v,$ and $w$. You don't get to choose these; your proof must go through for any choice of $u,v,$ and $w$.

Think of the pumping lemma as a game:

• Mr. Pumping Lemma gives you a constant $n$.
• You choose a word $w$ in the language of length at least $n$.
• Mr. Pumping Lemma gives you $x$, $y$, and $z$ with $xyz=w$, $|xy|≤n$, and $y$ not empty.
• Now you pick $r$.
• Mr. Pumping Lemma asserts that $xy^rz$ is also in the language.
• If he's wrong, you win.

You don't get to make Mr. Pumping Lemma's moves; he makes them, and your proof must present a strategy that wins even though Mr. Pumping Lemma is trying to beat you.

Answer 2

Your proof of irregularity is spelled out a bit confused as you start "I assumed it to be not regular and tried to prove that it is not regular". Actually, there is a pumping length for this language: If $z$ is a word of length $\ge5$ the it either contains a "5" in the first five letters and can be written as $z=uvw$ with $|u|\le 4$, $v=5$ and clearly also all $uv^kw\in L$; or it contains no $5$ in the first five letters, hence the first five letters are all "3" so that $z=uvw$ with $u=\epsilon$, $v=33333$ and clearly $uv^kw\in L$.