Complement of language

Question

What is the complement of language $L = \big \{a^nb^n, n\ge 0 \big \}$. Is it regular?

What about complement of $L = \big \{a^nc^nb^n, n\ge 0 \big \}$ ?

Answer 1

$L=\{a^nb^n\mid n\geq 0\}$ then $L^c=\{a^mb^n\mid m \neq n\}$(DCFL)$\cup$$\{(a+b)^*ba(a+b)^*\}$(Regular)-----

hence it is DCFL $\cup$ Regular hence DCFL. It may or may not be regular but here $L$ is not regular and hence its complement must also be not regular since regular languages are closed under complement.

$L=\{a^nc^nb^n\mid n \geq 0\}$ (CSL but not CFL) then $L^c=\{a^mb^nc^k\mid m \neq n$ or $n\neq k$ or $m\neq  k \}$$\cup$$\{(a+b+c)^*ba(a+b+c)^*\}$ $\cup$ $\{(a+b+c)^*ca(a+b+c)^*\}$ $\cup$ $\{(a+b+c)^*cb(a+b+c)^*\}$

---hence CFL

Comments

First one is fine ..

But in 2nd one..take a string 'ba' ..It is not accepted by the complementary language which should be accepted..

---

Edited..ok now?

---

Why not m!=k

---

m!=k is inclued in m!=n or n!=k

m!=k has 4 case-----either m=n then n!=k included

                                 or m!=n included

                                  or k=n then m!=n included

                                  or k!=n included

Actually m!=n,n!=k or m!=k...among these 3 only two check is suffiecient.

---

Thanks Kishalay

Answer 2

Complement of a^nb^n ={a^nb^m : m!=n } U { (aUb)*ba(aUb)*}

The given language is Deterministic CFL and not regular and the complement is also a DCFL and not regular language because DCFL is closed under complementation.

ii)Complement of a^nb^nc^n =a*b*c* - (a^n b^n c^n: n>=0)
                                                 
                                                 = a*b*c*  INTERSECT {(a^i b^j c^k|i=j)' U (a^i b^j c^k | j=k)'}
                                                 = a*b*c*  INTERSECT (a^i b^j c^k|i=j)' U a*b*c*  INTERSECT (a^i b^j c^k|j=k)'
                                                 = (a^i b^j c^k|i!=j)  U   (a^i b^j c^k|j!=k)
L={a^nb^nc^n,n>=0} is a NPDA but  the complement is CFL and  not regular

Comments

@Arnabi @thor ∪ {(a+b)*ba(a+b)*} why this part is needed in 1) 

Answer 3

for first part answer explained very well

https://gateoverflow.in/63645/toc