TOC-reg

Question

Complement of :  {aⁿbⁿ | n>=0} ?

Also tell if it is CFL or CSL?

Answer 1

Complement of a language L is defined as  L'  =  Σ* - L..This means all strings that can be made by the given alphabet except those in the language L should come in the language L'..

Given L = { aⁿ bⁿ | n >= 0 }

   So there are 2 such types of strings which wont come in the above L..

  a) Number of a's and number of b's should be different with the a's followed by b's..This is represented as : {aⁿ b^m | m != n}

  b) One inversion i.e. 'ba' and anything before and after it just to break the order of a's and b's in aⁿ bⁿ .This is represented as : 

    { (a+b)* ba (a+b)* }

 Hence  L' =  {aⁿ b^m | m != n}  ∪  { (a+b)* ba (a+b)* }

  Here the first part is DCFL and second part is regular..

  Hence the overall language is DCFL as DCFL union with regular is DCFL only..

  Hence the complement of the given language is DCFL..

Comments

Beautiful explanation :)

---

@habibkhan

I think you missed out the a,aa,aaa,aaaa...and b,bb,bbb,bbbb...am i right?

---

That is included in first part of my language itself as described above.. For : a, aa, aaa.....keep n = 0.. And for b, bb etc.. keep n = 1