The Gateway to Computer Science Excellence
0 votes

Is there any way to check whether a language is regular or not without using Pumping lemma?

in Theory of Computation by | 148 views
pumping lemma is used to prove that a non regular language is non regular.. its based on proof by contradiction.

and if u can write regular expression or create dfa than its regular,

if it accepts finite strings.
By practice it becomes easy to find whether the language is regular or not.
Yes just see if you can make a FA for the language given, watch knowledge GATE videos it has covered this well. With practice you will be able to know it.
i agree to u on this :p he is one of my fav. too :P
Thank You
If a language regular, then it definitely satisfies pumping lemma, but if pumping lemma satisfies, then language may or may not regular

2 Answers

+2 votes
First Just check if it is a finite language or not. Every finite language is regular language.

Now if it's infinite it still can be regular, so check if it compares any two counters. By counter I mean, count of the occurrences of any set of symbols. So if there's even one comparison of counters, it's non regular. Eg a^nb^n

In case there's no comparison between the counter but the counter itself is nonlinear then also the language is non regular. By nonlinear counter, I mean if the languages counts that if number of occurrences of 1 is a prime number, then it will be a non regular language. But if it's prime number from 0 to 1000 then it becomes a regular language because the language will be finite.

These are a few guidelines and the rest can be managed with practice.
by Active
0 votes

1. Check whether the language is finite or not. If its finite then it is surely regular.

2. If its not finite then there may be a case that its not regular.

3. Rules for checking if regular:

a) Check if there is any pattern in AP then its regular.

b) If there is any irregular pattern like in GP or in terms of prime then not regular.

c) If automaton requires saving of infinite length string then comparing then its not regular.

d) Modular counting or modular division is always regular.

4) Pumping Lemma is negativity test means

a) If passed then language may or may not be regular.

b) If failed then language is definitely not regular.

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,223 questions
59,818 answers
118,091 users