0

find whether string with even number of zeros is a) context free b)regular

a) using pumping lemma for CFL....it can be represented as e(0n)e(0n)e. so , it's a CFL.

b) it can be represented as (00)* in regex. So, i think it's a regular language. But, I am not able to prove the same using pumping lemma for regular languages

Any help would be much appreciated. Thanks!!

claudius
  • 1,112
  • 1
  • 10
  • 23
  • `0^n0^n` for n >= 0 *is* a regular language that can be represented by RE `(00)*`, *it is* `0^n1^n` is not regular (but a CFL). – Grijesh Chauhan Apr 07 '14 at 11:18
  • 1
    `"But, I am not able to prove the same using pumping lemma for regular languages."` You can't use pumping lemma to proof the language is a regular language. -- We use pumping-lemma to proof the language is *not* a regular language. It is necessary but a sufficient property of regular language. You question read: [Pumping lemma for regular language](http://stackoverflow.com/questions/14705091/pumping-lemma-for-regular-language) – Grijesh Chauhan Apr 07 '14 at 11:24
  • 0^n1^n is not always in L = { string with even 0's } or I am wrong? – llazzaro May 11 '15 at 00:10

0 Answers0