How to check if a language is not regular?

Question

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?

Answer 1

Yes your answer is 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 .