0
$\begingroup$

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?

$\endgroup$

1 Answer 1

0
$\begingroup$

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 .

$\endgroup$
6
  • $\begingroup$ 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 $\endgroup$ Nov 8, 2020 at 13:59
  • $\begingroup$ 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 . $\endgroup$
    – Anwar
    Nov 8, 2020 at 14:16
  • $\begingroup$ Thank you!!! <3 $\endgroup$ Nov 8, 2020 at 14:24
  • $\begingroup$ also what do you mean by FA? Finite state machine? $\endgroup$ Nov 8, 2020 at 14:27
  • $\begingroup$ Yes a Finite Automaton $\endgroup$
    – Anwar
    Nov 8, 2020 at 14:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.