The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
106 views

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

in Theory of Computation by (137 points) | 106 views
+1
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.
0
By practice it becomes easy to find whether the language is regular or not.
+1
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.
0
i agree to u on this :p he is one of my fav. too :P
0
Thank You
0
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 (3.3k points)
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.

by (111 points)

Related questions

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
50,309 questions
55,743 answers
192,231 comments
90,499 users