FOR FREE MATERIALS

Shortcut Prove : Not Regular

 

In a competitive examination, if we have a question like that 

 

 

The above statement is

 

a) True 

b) False 

c) May or may not true

d) Undecidable 

 

Or another question you can consider

 

 

a) Regular 

b) DCFL 

c) NCFL 

d) CSL

 

In both case, we do not have enough time to solve it by pumping lemma to prove this language is not regular.

 

So, there are some short cut methods by which you can say a certain language is not regular with pumping lemma.

 

1. Finite language is always regular and we can write a regular expression for that language.

2. For infinite language it may or may not be regular.

 

Let L = {ab, abab, ababab, …….} if this language is a regular or finite language then definitely it has a Finite Automata (Finite Automata has finite no. of states).

 

An infinite language is regular if and only if it accepts by a finite automata (with a finite machine) and it is possible by making loop in the finite automata. 

 

Like:

 

 

And on the loop, there should be a pattern if there is no such pattern then it is not a regular that says pumping lemma.

 

We can identify in a general way by the basic concept of inclusion.

 

 

Without pumping lemma, we can directly say that it is regular because it has finite automata.

 an | n  1 at least one a means aa*.

 

 

 

It is regular because n is bounded or finite so, in any cases, if n is bounded then it is a regular language.

 

 

Special Cases: 

 

 

An infinite language that is regular must have a loop in Finite Automata (FA) with a homogeneous pattern i.e. if we repeat this pattern we will get entire the set of strings of the given language.

 

 

If we see this set, it has a common pattern i.e. every power of a is always multiply of 2 i.e. the difference between every string length is 2

 

So, in that case, strings length is in A.P and difference is common then it is a regular language.

 

Whenever string length is in AP and pattern is homogeneous then this language is a regular language.

 

 

If you see the pattern of strings is: 

 

 

Then there is no homogeneous difference so, it is not in AP. Hence it is not Regular Language.

 

 

It is also is in A.P, it is regular.

 

 

It is also not in A.P, it is not regular. But from language identification, we know any non-linear power is never a regular language. It is always Context Sensitive Language (CSL). (See Chapter Language Identification

 

 

It is also not in A.P. 

 

 

It is not regular.