CODEWITHSUNDEEP
regular-languagefinite-automataautomatapumping-lemma
Rahim Khalid
Rahim Khalid

Reputation: 469

Proof the language is regular or not regular using Pumping lemma?

Can any one help to figure out that L = { am bn, m ≥ n + 2, m ≤ 3 } is regular or not using pumping lemma, It seems to be a bit difficult to prove.

I have tried to used pumping lemma and it shows that it is regular language but i am really confused that is this right or not.

Upvotes: 0

Views: 1944

Answers (2)

new_bee
new_bee

Reputation: 101

we cannot use the pumping lemma for proving language is regular.To prove a language is regular we should design DFA for that language

Upvotes: -1

Grijesh Chauhan
Grijesh Chauhan

Reputation: 58251

I have tried to used pumping lemma and it shows that it is regular language but I am really confused that is this right or not.

First note, the pumping lemma can be used to proof that "certain language is not a regular language". But we can not use pumping lemma to proof that "certain language is a regular".

Yes, the pumping lemma for regular languages describes an essential property of all regular languages, and if a languages don't satisfy the conditions described by pumping lemma or say don't satisfy pumping lemma property then that language is actually not a regular language, But the converse of this is not true!! &mdash- there are "languages those satisfies pumping lemma's conditions and may still be non-regular", means:-

Pumping lemma is 'necessary but not sufficient condition' for a language to be regular.

This is something like: every engineer is math student - so if a student is engineer we can say that he knows math, but their are math students those don't know engineering. (just giving you an example to explain)

From your question, I have impression that you don't understand basically - "what is a regular language?".

Unlike pumping lemma for regular languages, we need to learn some other characteristics of regular languages - finding them in a language proofs that the language is a regular language. If you can represent a language using finite automata or/and regular expression that proofs that the language is a regular language.

Now, come to your original question:

How to proof that language { am bn, m ≥ n + 2, m ≤ 3 } is regular or not?

Because neither 'm' or 'n' can be negative (a string without occurrence of any symbol is possible eg. empty string1, but a string with negative occurrence of language symbols is not possible) and according to condition "m ≥ n + 2", 'm' is always greater than 'n' — so minimum value of 'm' (when 'n' is 0) is 2. From second condition "m ≤ 3", maximum value of 'm' is '3', and so 'm' can be either 2 or 3.

If you again notice fist condition: "m ≥ n + 2" for m = {2, 3} possible values for 'n' can be:

  • for m = 2, n can be 0 and that makes string 'aa'.
  • for m = 3, n can be 0 or 1 and that makes strings 'aaa', 'aaab'.

So, it came that the language is a finite language e. only consists of three strings. Every finite language is a regular language, check venn diagram:

See venn-diagram

(to lean more about this read: Finiteness of Regular Language)

Regular expression for your language L = { am bn, m ≥ n + 2, m ≤ 3 } would be aa(a + Λ)(b + Λ), hence it is proofed that language is a regular language.

1 a string without occurrence of any symbol is called empty or null string in formal languages, in most of formal language books symbol Ɛ for empty string.
Λ is empty symbol.

Upvotes: 3

Related Questions