# How to check if a language is not regular?

I have the given regular language and i am suppose to check if it is regular and if it is, to provide a regular expression

However, if the language is not regular i have to prove using the "Pumping Lemma" that it is not regular

• it is regular if, it can be represented by a finite state automata (FSA)

• or, if it can be represented by a regular expression

L = { a^2 b^n c^m , where n,m >= 0 }  Alphabet is {a,b,c}


My thoughts:

At first glance, i thought this language is regular because it can be represented by a regular expression. The regular expression that i would propose would be a^2 b^* c^*, is this correct?

Language L generates strings that begin with 2as followed by any number of bs then followed by any number of cs

Your regular expression represents L correctly

It is also worth reminding how the pumping lemma works , if a string in a language L cannot be pumped , then L is non-regular , however some languages can still fool the pumping lemma

Consider the language F = {a^i b^j c^k| i,j,k ≥ 0 and if i = 1 then j = k}. Which appears as a regular language in pumping lemma but is actually non-regular

This is why there are other methods to prove that a language is non-regular

For example to prove F is non-regular you should remember that regular languages are closed under complement (if F is regular then F' is regular too ) , then by the pumping lemma you can show that F' is non-regular and thus F is non-regular , sometimes closure under intersection is useful too

Finally you should try to get an intuition on the language , clearly L needs only finite memory to check the number of as , there can be any number of bs and cs and the FA does not need to remember the number of bs and cs , an intuition is a good first step .

• Thank you, also is there a reason why this language cannot be pumped? for example, if i tried to use the pumping lemma to test if this language was irregular, why wouldn't that work – nodejsbeginner Nov 8 '20 at 13:59
• That is a great question that concerns the use of the pumping lemma , simply as editted in the answer ,if a language L generates a string which can not be pumped then this language is non-regular , all regular languages pass the pumping lemma as well as some of the non-regular languages , this is why the pumping lemma can be used to prove a language is non-regular but never to prove a language is regular , obviously , since L is regular it passes the pumping lemma , but still this is not an evidence that it is regular ! Finally L can easily be, pumped you may want to try to . – Anazz Nov 8 '20 at 14:16
• Thank you!!! <3 – nodejsbeginner Nov 8 '20 at 14:24
• also what do you mean by FA? Finite state machine? – nodejsbeginner Nov 8 '20 at 14:27
• Yes a Finite Automaton – Anazz Nov 8 '20 at 14:37