1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Certainly it's possible to know if a language is regular without knowing its grammar. Suppose someone hands you some awful finite automaton with 10,000 states and says “Let $L$ be the language accepted by this automaton. Is $L$ regular?” You can immediately answer “yes!". $\endgroup$ – MJD Sep 14 '15 at 18:15
  • $\begingroup$ @MJD: Agree with your conclusion, but: in that particular case it would only take 10,000 time to write down a regular grammar for the language. $\endgroup$ – Henning Makholm Sep 14 '15 at 18:20
  • $\begingroup$ And it only takes $O(1)$ time to decide if $L$ is regular, without writing down the grammar. $\endgroup$ – MJD Sep 14 '15 at 18:21
  • $\begingroup$ @MJD: My point is just that the gap between "being given a finite automation" and "knowing a grammar" is fairly small and the example is therefore not very striking (to me, at least). On the other hand we could say "the set of decimal representations of numbers that have at least one 23-digit prime factor" and almost immediately know the language is regular -- but still be very far from knowing a grammar for it. $\endgroup$ – Henning Makholm Sep 14 '15 at 18:27
  • $\begingroup$ That is a better example, thanks. $\endgroup$ – MJD Sep 14 '15 at 18:53
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ let say : Mr. Pumping lemma gives me constant n=4, Then I can chose a word with length at least 4, so I chose 4 as my length and the word as '3333' Now if Mr. Pumping lemma gives me x=3, y=3, z=33 Now I get to chose r, so I chose 4. Mr.Pumping lemma asserts that the word 3(3333)33 is in the language, which is wrong. Does this mean Mr.Pumping lemma will always give me n>=5?? $\endgroup$ – user10859 Sep 15 '15 at 15:37
  • $\begingroup$ Right, Mr. P's constant is at least as big as the number of states in the smallest finite automaton that accepts $L$. In this case, Mr. P might give you $n=5$ and then if you choose $\mathtt{33333}$ he will pick $x=\epsilon, y=\mathtt{33333}, z=\epsilon$, and then no matter what $r$ you choose in step 5, you lose. Mr. P has a winning strategy in this case because the language is regular. $\endgroup$ – MJD Sep 15 '15 at 16:19
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.